Week - 15

Quiz on trees:

1. Given two binary search trees, check whether or not they are identical.  Identical meaning that both the structures (node location, height, etc.) and the values contained at corresponding nodes are matching. 
2. Given a value k, and a binary tree T, print out all values at k distance from the root.
3. Given a binary search tree T and an integer k, find the node in T with the closest value to k.  E.g. if the binary tree contained 20, 23, 30, 34, 40, 51, 54, 60, 70, and k = 31, then the solution should return the node containing 30.  (We will deal with integers in this case, so no generics.)

 Answers link

Week - 14

Post order traversal of a BST: Link to code

Quiz

Week-13 : Correction in priority queue

Today, we discussed about implementing priority queue using ArrayList and LinkedList. While using ArrayList, we don't have to shift elements after removeMin(). I have explained a better solution below.

When we are using

Unordered ArrayList:

• add(element e) => O(1)
• peekMin() => O(n)
• removeMin() => O(n)
• Here, removeMin() requires finding the min value => O(n), removing it and then, shifting the elements will take O(n).
• A better solution: Instead of shifting, just replace the gap with the last element of the ArrayList. This can be done in constant time [O(1)].

Unordered ArrayList with index value of min:

• add(element e) => O(1)
• peekMin() => O(1)
• removeMin() => O(n)
• Again instead of shifting, replace the gap with the last element. But, we have to keep track of the index of min. To update the min index, we must traverse the list. This will take O(n) time.

Week - 13

Sets & MultiMap

1. Link to presentation slides
2. Set interface code
3. ListSet code

Week-12 - Midterm II: Solutions

Problem 1:

In order to get a worst case running time of O(n^2), we should draw a tree in such a way that, depth() function is called at each level. Therefore, a tree with many leaves will run for the worst case.

Problem 2

ArrayList : O(n) for remove => O(n^2) run-time.
LinkedList: O(1) for remove => O(n) run-time

Reference: ArrayList Vs LinkedList

Problem 3

Code

Problem 4

Inorder and Breadth first traversal.

Problem 5

Code

Week-11

Class cancelled.

Week-10

We discussed 2 topics:

1. HashMap example: Roman Calculator example
2. Implementing stack using 2 queues. Link for more details
3. Quiz

Week-9

1. We discussed Element Uniqueness problem using HashMap.
2. Implemented a queue using 2 stacks. Link to the code on StackOverflow
3. Quiz

Week-8

We discussed HW-5.

1. Remove Odds
2. Concatenate List
3. HW_5 Problem 3 & 4

Basic operations in a Positional List.

Few questions over the past few weeks

StringBuilder Vs StringBuffer

StringBuffer is synchronized, StringBuilder is not.

Both are mutable

The object created through StringBuffer & StringBuilder are stored in the heap .

StringBuffer is slow but thread safe . Due to this it does not allow two threads to simultaneously access the same method . Each method can be accessed by one thread at a time .

StringBuilder is fast as it is not thread safe.

Adding variable watch

While you're in the debugger go Window -> Debugger -> Variables

You will have <Enter new watch> written there. Type the variable you want to watch there and you can track it from there. 

Week-7

Discussion about the midterm questions.

Week-6

No class.

Week-5

Links for the Factorial & Binary Search code we discussed in class last week:

1. Factorial code
2. Simple Binary Search without recursion.
3. Recursive Binary Search which returns index of the target element.

Some good videos to learn about Binary Search:

1. Binary Search - I
2. Binary Search - II

Link for Week-5's presentation slides.

Sorry for the delay. 

Week-4

Examples for Arrays comparison and clone

1. Array equals example-1
2. Array equals example-2
3. Array clone example
4. Deep clone example

This week's presentation slides.

Quiz time

There will be a quiz tomorrow for 20 minutes before the end of class. It will be open book and open notes. No electronic devices are allowed.

Note: Attention to details is very important. 

Week - 3 Exceptions and Files

Important points from week-3 discussion session:

• Quiz on Thursday, 2/12/2015
• We discussed about exception and it's use. 
• Different ways of writing an exception. 
• A simple file read/write.

Here are the links to the programs we discussed:

• Without exception
• Simple try-catch
• try with multiple catches
• Nested try-catch
• Simple file read/write
• File read with BufferedReader

Link for yesterday's presentation slides.

Have a great weekend :)

Week - 2 - More about Java

Loops:

There may be a situation when we need to execute a block of code several number of times.

Given below are the links for the programs we discussed today:

• while loop
• do..while loop
• foreach loop 
• switch 
• continue 
• StringBuilder
• TheMain class

Link for today's presentation.

Welcome to Data structure II - Week - 1

Welcome back from your winter break.

Here is a link to the presentation document - Link to download