How to Study for CS2321 Midterm

Author: Ahren Sitar

Data Structures Fall 2010

Introduction:

This web page is a preparation guide for students in the MTU data structures course and should not be a last minute resource. Properly preparing for any class must be done at least three to four days before the exam. Many students that are CS (Computer Science) or CpE (Computer Engineering) majors often struggle with finding appropriate ways to studying for non-programming exams. This web page is designed to help you study for those types of exams. On this web page you will be briefed on what topics are covered for the midterm and how to appropriately prepare for the exam. This page will also go over a couple examples of questions asked on past exams.

Course Material:

This section is a quick review of the material that will be on the exam. For more in-depth notes, please refer to the outside sources and help section or your own personal notes.

· Asymptotic Analysis

· Priority Queues and Sorting

· Tree Implementations

· Heaps, Heapsort, In-place Heapsort

· Greedy Algorithm & Huffman Encoding

· Divide & Conquer

· Quick Sort

· Sort Complexity, Bucket Sort

· Maps and Dictionaries

· Hash Tables and Collisions

What to study:

This is where most students have trouble. What should you study and how should you go about doing it? In general there will be six question types that you should become familiar with in order to pass your exam. These are:

1. Cost tables

2. Reading pseudo code & giving time complexities

3. Writing pseudo code

4. Short answer

5. Illustration of algorithms

6. Real life problems/examples

How to study:

Knowing what to study is half of studying, the other half is knowing how to study. Studying first off should never be done last minute, this not only cut the amount of time to prepare way down but also does not give your brain enough time to put what you have learned into memory. Always give yourself plenty of time to study before an exam, three to four days should be a minimum. Studying does not have to be a 2 to 3 hour straight period, even 30 to 40 minutes a day should be plenty of time to let what you learned sink into your brain. Plenty of sleep is also an important key to performing at your best. If you find yourself having trouble with any of the topics you study please refer to the sources at the bottom of the page for help.

Cost tables – When reading cost tables, students should understand three things: the expected case time complexity, the worst case time complexity, and the sequence size for the different types of sorting algorithms [3]. Here is a good example of what to expect.

Sort Algorithm	Time Complexity		Sequence Size
	Worst	Expected
Insertion	n²	n+k* (exact time)	small
Merge	nlg(n)	nlg(n)	large
Quick	n²	nlg(n)	medium
Heap	n²	nlg(n)	medium
Bucket/Radix	n²	n+N	medium

*k is number of inversions

Memorization of the times and sequence sizes is a poor way to go about studying for this section. It’s better to understand each algorithm to know what makes them different and why they would run at these times. If you approach learning the cost tables in this manner compared to memorizing them, you will be better off in sections to come.

Reading pseudo code & giving time complexities – This type of question has been covered on many exams in prior CS classes and should be familiar how to approach it. As a quick recap, pseudo code is “a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of a programming language, but is intended for human reading rather than machine reading” [1]. Here is a good example of pseudo code where the time complexities can easily be deciphered:

Algorithm: int Sort(Character Array T, Character Array P)

Input: A array of n numbers

Output: A sorted

For i ß 1 to n – 1 do

X ß A[i]

J ß i – 1

while 0 <= j and x < A[j] do

A[j + 1] ß A[j]

j ß j -1

end while

A[j + 1] ß x

end for

return A

Time complexity/cost: ?

In this example you need to interpret what the time cost is for each line of code performed and give the big O notation for the whole algorithm. In this particular example, lines 2,3,5,6, and 7 run at constant time O(1), line 1 runs at linear time O(n), and line 4 runs at quadratic time O(n²). Therefore, your big O notation should be O(n²)[3].

Writing pseudo code – Writing pseudo code is as easy as reading it, if not simpler. A very good way to practice writing pseudo code for your exam is to go through each type of sorting and traversal algorithms covered in class and write pseudo code for each of them. If you can do this, look at the code and see if you can approach this problem in more than one way. A good example of this is trying to write the pseudo code for the Depth First Search (DFS) algorithm iteratively and recursively. It is important to be able how to recognize and approach a problem in more than one way. Let us do an example from a past exam, where you have to write pseudo code for an iterative algorithm to print a linked binary tree level wise.

Levelwise(tree T)

Make Queue Q of nodes

Q.enque(t.root)

While Q is not empty do

V ß Q.deque

If v has left then Q.enque(v.left)

If v has right then Q.enque(v.right)

Short Answer – Short answer questions should be one of those exam question types that you are familiar with. These are very common on most exams and will be on your CS exam as well. What should you expect from these questions? Most short answers in CS will be concepts that you have to define in your own words. Examples would be asking for the definitions and real life examples of a map, dictionary, greedy algorithm, priority queue, etc. These questions are very straight forward and should come as no surprise when asked a question of this sort.

Illustrate Algorithms – This section of the exam will be based completely on examples that have been performed in class. Sorts are what you will need to know how to illustrate. These illustrations may ask you to traverse maps and/or insert and remove from different types of data structure containers. Here are a couple example of what you might be expected to do:

Real Life Problems – This is the hardest portion of the exam because no one is sure how to study for this section. However, I will provide steps to help prepare you for this portion of the test with a couple example problems. This way you can get an understating of how the question will be formatted and what you can expect so that there are no surprises. So how should you go about studying for this section? One method is to make your own questions. Look at real world applications and try to solve them.

Here are four points that should be followed when answering the real life problem:

1. Read and analyze the problem

2. Choose data structure and algorithm

3. Choosing an implementation

4. Cost

When reading and analyzing the problem, be sure to read through multiple times to make sure you understand what is being asked. Then choose the data structure and algorithm that would be best for this situation and give your reasons why. Remember that it’s very important to explain your reasons for your choices. Then give the total time and space complexity for your problem based on the DS you choose and how you choose to implement it. Again, remember to explain your choice. Here is an example of a past problem that should give insight on what to expect.

Example.

A thief has hired you to write a program for his PDA, which the thief has during a theft. The thief plans to steal from a chemistry store. The thief knows the possible chemicals at the store, and their value per pound, but he does not know the quantity of the chemicals at the store. The thief can only carry 100 pounds before falling from exhaustion. The thief wants the program to tell him how much of each chemical to take. Naturally he wants to steal the maximum value possible for his booty. Please be sure to specify the algorithm, data structures, and cost.

Outside Sources and Help – Data structures is looked at as one of the toughest classes that CS and CpE majors will have to take. Therefore, it is extremely helpful to know where to go for help on programming or studying for and exam. If you are not aware of what is available on campus for help, here is a list with links:

· Your Teacher, look for office hours (http://www.csl.mtu.edu/cs2321/www/Syllabus.htm)

· Your TA, again look for office hours (http://www.csl.mtu.edu/cs2321/www/Syllabus.htm)

· CS learning center coaches, mostly used for programming help but do offer great help for studying (http://www.cs.mtu.edu/lab.info/lab.hours/learningcenter.html)

· Your fellow students

Here is a list of sources that are always available:

· Your Data Structures & Algorithms in JAVA book

· Google (a programmers best friend)

· Wikipedia

· Youtube.com for visual demonstrations

· CS 2321 Course Schedule Webpage (http://www.csl.mtu.edu/cs2321/www/Schedule.htm)

Sources:

[1] “Pseudo Code,” Wikipedia.org, November 2010. http://en.wikipedia.org/wiki/Pseudocode

[2] R. Pastel, “CS2321 Data Structures,” http://www.cs.mtu.edu/cs3221

Accessed Nov. 22, 2010

[3] A. Sitar, Notes and Midterm for CS2321, Data Structure Midterm, Michigan Technological University. Fall Semester, 2010.