Term Taken: 2019 Spring

Instructor (Class A): Prof. Irwin King Kuo Ching

# Grading Scheme

- Written Assignments (5%)
- Programming Assignments (20%)
- Written Midterm Exam (20%)
- Programming Midterm Exam (35%)
- Written Final Exam (20%)

# Textbook

Data Structures and Algorithm Analysis in C (2nd Edition), *Mark Weiss*, 1997.

# Topics Covered

- Big O, Omega, Theta Notation.
- Linked List.
- Stack.
- Queue.
- Tree: Binary Search Tree, AVL Tree, B-Tree, Trie.
- Heap.
- Hash: Separate Chaining, Linear/Quadratic Probing.
- Bubble Sort, Insertion Sort, Selection Sort.
- Merge Sort, Quick Sort, Shell Sort, Bucket Sort.
- Graph: Topological Sort, Breadth-First Search, Depth-First Search.
- Dijkstra’s Shortest Path Algorithm.
- Minimum Spanning Tree: Prim’s Algorithm, Kruskal’s Algorithm.
- Network (Maximum) Flow.

**Additional Materials for ESTR:**

- Disjoint Sets.
- Quick Select.
- Dynamic Programming.
- String Matching Automata (KMP Algorithm).
- Bellman-Ford Shortest Path Algorithm, Min Cut Problem.
- (Brief Introduction to) Traveling Salesperson Problem.
- Computational Geometry: Convex Hull Problem, Quadtree.

# Brief Review

- Worth Taking.
- VERY Time-Consuming.
- Pretty Challenging.
- Fun.

# Review

This is a required course for computer science major. Since data structures are the basic building blocks of computer science and programming, it is extremely important to MASTER this course.

The material itself isn’t difficult, and the data structures covered are pretty straightforward. However, this course is quite challenging because it requires us to master both the abstract data types and the implementation using C language. Prof. King will cover only the high level description and operations of the data structures, so we have to spend a LOT of time coding the data structures and of course, debugging. So in my opinion, this course works as a filter for CS students, you will become a “real” CS coder after taking this course.

There are programming assignments every two weeks. Each programming assignment consists of three ACM-competition-formatted problems with increasing difficulties (but they are still far easier compared to actual ACM problems). ESTR students are asked to solve all three problems while the third problem serves only as a bonus for regular students. We have to submit each problem through PC2 system (used for ACM competitions), so submission time is also a grading factor. I got heart attacks before each submission session.

The written assignments are quite easy, yet it also takes plenty of time because we have to illustrate each step of certain data structure operations by drawing, drawing and drawing. Each written assignment adds up only 1% of the final score. For each written assignment, you will get a full 1% if you “work hard”, otherwise you get 0%. There are no explicit guidelines but if you show each step clearly, you will very likely get a solid 1%.

The midterm exam and final exam have very similar formats and are pretty easy, you are asked to demonstrate the steps of certain operations (like in the homework), show the time/space complexity of some operations, develop some simple algorithms, etc. Since the final exams have been pretty much the same for over 5 years, doing past-paper is ^{11}⁄_{10} recommended.

Because most people got similar scores for the midterm and final exams, the programming midterm is what makes a difference. The programming midterm is a 3-hour-session mini-contest on a lovely Friday night, we were given 7 ACM-styled programming problems like those in programming assignments. They were intentionally designed to be challenging, so the class solved only around 3 problems on average. You score 60 out of 100 if you solve at least one of the seven problems, so don’t worry. The final score will be ranked and the top students will receive prizes at the end of the semester. I consider the best way to prepare for the programming midterm is to grind Leetcode problems, since the last couple problems came from Leetcode Medium and Hard for this year. Also, since the programming midterm is open-book, open-note, printing C implementations of ALL data structures covered in class is a MUST!!! (Make sure the code in your cheatsheet is 100% correct, or you will suffer. Very Much.)

Prof. King teaches very well and likes to walk up to the seats and ask student questions. The upside is that students may get more prepared for each lecture, but the downside is that it takes too much time for the asking/answering so he tends to rush towards the end of the semester.

You will spend up to 5-10 hours on average each week if you plan to master (get an A in) this course, but it is definately worth since this course is a stepping stone to futher studies in CS, not to mention Big-N tech companies do data structure interviews for their hiring process.

# I’ll Give You All I Have Here

C Implementations of Common Data Structures

Solutions to the Programming Assignment Problem Sets

My Cheatsheet for Programming Midterm

(Some implementations are pretty stupid, I know. So make your own cheatsheet!)

### Past Programming Midterm

I happen to know some problems in programming midterms of past years.

(Notice that the first problem of each programming midterm is easy as heck, if you cannot solve a single problem, you might as well re-ponder the meanings of your life.)

##### 2014

- Check if a string is palindrome.
- Leetcode problem 169.
- Deisgn a Max Heap supporting the following operations:
`find-max`

,`insert`

,`delete-max`

, and`change-max`

(change the value of the maximum element). - Given the pre-order and in-order traversals of a binary tree, return the leaf nodes of this binary tree.
- Josephus problem: Given
`n`

people and the execution gap`m`

, return the execution sequence. - Leetcode problem 155.
- Given a dictionary containing several words. Your task is to answer queries asking whether a single word occurs in the dictionary.
- Determine whether a permutation can be generated by using two stacks.

##### 2016

I don’t have the exact problem set for this year, so some problem descriptions may seem incomplete.

- ? (Probably something very simple, which isn’t worth mentioning.)
- Print a pyramid of numbers (?)
- Given a sequence of parentheses, determine whether it is valid. (That is whether each
`(`

is matched with a`)`

.) - Similar to 2014 problem 5.
- Color of balloon. (String hashing for strings, representing each color. Similar to 2014 problem 7.)
- Given the pre-order and in-order of a binary tree, output the level-order traversal (breadth-first search).
- Receiving input from a number stream, return the median of the stream anywhere in the middle of the stream.

##### 2019

- Given a sequence of integers, return the difference between the sum of all odd numbers and the sum of all even numbers.
- Given a playlist of length
`m`

with the initial song labels as`1,2,3,...,m`

, two operations are allowed:`PLAY`

and`REMOVE`

. The`PLAY`

operation plays the current song in the playlist and then places it to the back of the playlist. The`REMOVE`

operation removes the currently first song from the playlist and never plays it again. Return the songs being played according to the given operation sequences. - Evaluate prefix expressions with operators +, -, *, / for positive integers. Return “division by zero” you encounter a zero divisor.
- Leetcode problem 378.
- Leetcode problem 3.
- Leetcode problem 124.
- Leetcode problem 1000.

(Seems like the TAs went full Leetcode this year…)