Core Exam Analysis – Part 4 [Algorithm]

This part is the most important field in Core Exam.
Whether this course has 3/8 problems in the exam or the quantity you need to read, algorithm is the key to pass it.

I think in NYU CS, if you pass the Core, then you will have the same conclusion like me.
Let’s take a look on the web page,

  • Analysis of the correctness and running time of algorithms.
  • Basic data structures: arrays, stacks, queues, linked lists, binary trees.
  • Recurrence equations.
  • Sorting algorithms: mergesort, binsort, quicksort, heapsort.
  • Selection. Binary search. Hashing.
  • Binary search trees and balanced trees.
  • Graphs: spanning trees, shortest paths, connectivity, depth-first search, breadth-first search.
  • Algorithm design: dynamic programming, divide and conquer.

But, from the history of the exam, some parts are very important than the others.
In my experience,

1. Dynamic Programming in different cases. <- Very Important
2. DFS/BFS search, Graph
3. Topological Sort
4. Divide and Conquer
5. Recurrence
6.  Tree structure.

I would like to make some comments to the preparation in Algorithm. At least I think this time I am confident after the test of Algorithm. (Although I don’t know the score in this part)

1. Dynamic Programming
In this part, student needs to know the detail procedure of how to solve a problem.
You need to be trained with the sense that when you look at the problem description, you know it’s D.P. (I will use DP instead of Dynamic Programming)

Second, you need to know how to build the parameter and the recurrence.

Finally, you might need to solve the time complexity in different operations.

Some examples :
1. Greatest Common Sequence(GCS) – Such as article letters weight, DNA sequence match.
In addition, the problem may ask you to provide a look-up table to improve the efficiency.
Other problems like, Tree Inorder, Wood cut-best profit, backpack problem, matrix multiplication(original, look-up table, and intermediate/the root) in pseudo code, president election vote / ads problem, etc.

Those problems are extracted from 2000~2007 Core Exam. You should take time to read/understand it.

2. Graph
Especially, Floyd-Warshall Algorithm. This algorithm has different “mutation”. Ex: Only two-edges, exchange the loop parameter order, use intermediate, solve first, second shortest path, solve the total count of the path.

BFS/DFS are implemented in some problems, not only the theorem itself.

Of course, I would suggest to take the whole algorithm exam sheets. And, if possible, take the course of Professor Siegel- Fundamental Algorithm.

If you can get more score on Algorithm, you are more close to pass the Core.
Mostly, students don’t like Algorithm. It’s very hard in some parts. Especially in DP, you may spend a lot of time and get nothing. But if you take the course, it would help a lot.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s