In the blog, I would like to share the nearly one-month preparation for the Preliminary Exam. It is a pretty tough and exciting experience. Since it is the first time I take part in exams of specialized courses in English and online and I need to overcome the time issue that taking the exam from 1 a.m. to 7 a.m., it sounds pretty difficult and terrible. But after I finish the writing exam and raise my head to see the sun rise, I think it is deserved.
Our prelim exam includes two part: Writing exam and Oral exam. The details and exam references are listed here.
In the writing one, we will take three exams including Computer Organization, Algorithm and Operating System. Each exam costs one and a half hours. As to the preparation, I concentrate on the books since it is the only official materials. I review the whole required chapters of each book twice. And I write a summary for each important ideas and concepts to help me to remember and review.
Computer Organization
As to the Computer Organization, the book covers the following main domains. The book introduces lots of details since different systems use different techniques. But it is not important and I just skip the implementation parts and real world examples.
- Chapter One: Introduction to computer organization. Some performance and efficiency calculation problems. Amdahl’s Laws.
- Chapter Two: MIPS Instructions.
- Chapter Three: Arithmetic.
- Chapter Four: Processor, datapath and related hazards.
- Chapter Five: Cache. Virtual Memory.
- Chapter Six: Parallel processors. Multithreading and multicore.
The exam is straightforward and not hard as I except. It asks questions about the key concepts and not many implementation details such as Windows, Solars and Linux are required.
Algorithm
As to the Algorithm, the required book is the classic one Introduction to Algorithm. I spend many times on it because I want to take the opportunity to review and enlarge my algorithms’ knowledge. The required chapters includes:
- Foundations:
- Complexity.
- Divide and Conquer: The maximum-subarray problem and Strassen’s algorithm for matrix multiplication.
- Recursion Tree, Substitution Method and Master Method.
- Randomized algorithm.
- Sorting:
- Insertion sort and Merge sort.
- Heapsort and Quicksort.
- Counting sort, Radix sort and Bucket sort.
- Randomized select algorithm including Finding maximum and minimum.
- Data Structure:
- Elementary data structures: Stacks, Queues, Linked List, Pointers and Objects, Rooted trees.
- Hash Table.
- Binary Search Tree.
- Advanced Design and Analysis Techniques:
- Dynamic Programming:
- Rod Cutting.
- Matrix-chain multiplication.
- Longest common subsequence.
- Optimal binary search trees.
- Greedy Algorithm:
- Activity selection problem.
- Huffman codes.
- Dynamic Programming:
- Graph:
- Elementary Graph Algorithms:
- Breadth First search.
- Depth First search.
- Topological sort.
- Strongly connected components.
- Minimum Spanning Trees:
- Generic-MST.
- Kruskal’s algorithm.
- Prim’s algorithm.
- Single-Source Shortest Paths:
- Bellman-Ford algorithm.
- Directed Acyclic Graph Shortest Paths.
- Dijkstra’s algorithm.
- Difference constraints.
- All-pairs Shortest Paths:
- Faster-All-PAIRs-Shortest-Path Algorithm.
- Floyd-Warshall algorithm.
- Johnsons’ algorithm
- Maximum Flow:
- Ford-Fulkerson Method.
- Edmonds-Karp’s Algorithm.
- Elementary Graph Algorithms:
- NP Completeness and Approximation Algorithm.
It is pretty hard to write pseudocode on Canvas so I am out of the time in the exam. The exam contains 7 questions. The first three are about algorithm running time. The middle two are about linked list insertion and sorting. The final two need to use graph algorithm to find the shortest path.
Operating System
As to the Operating System, I spend over half of my preparing time on it. I learn some implement details written in the book while the exam also does not cover. But I still enjoy the learning since I believe it is useful for my future career.
- Process:
- Process Control Block
- Scheduler
- Operation: Creation and Termination.
- Communication.
- Threads:
- Parallelism and Concurrency.
- Multithreading Models.
- Process Synchronization(Important):
- Critical section problem.
- Mutex Lock.
- Semaphores.
- Monitors.
- CPU Scheduling:
- Scheduling Algorithms.
- Multiple Processor Scheduling.
- Real-time CPU Scheduling.
- Deadlocks:
- Necessary Conditions.
- Resource-Allocation Graph.
- Prevention, Avoidance, Detection and Recovery.
- Main Memory:
- Contiguous Memory Allocation.
- Segmentation.
- Paging.
- Translation look-aside buffer.
- Hierarchical Paging.
- Virtual Memory:
- Demanding Paging.
- Copy-on-Write.
- Page Replacement algorithms.
- Allocation of Frames.
- Memory Mapping.
- Allocating Kernel Memory.
- Mass Storage Structure:
- Magnetic Disk.
- Disk Scheduling.
- Disk Management.
- Redundant Array of Independent Disks.(RAID)
- File-System Interface:
- Operations.
- Access methods.
- Directory.
- Mount.
- File Sharing.
- File-System Implementation:
- Layered File System.
- Virtual File System.
- Directory Implementation.
- Allocation Methods.
- Free-Space Management.
- I/O System:
- Interrupt Vector.
- I/O Hardware.
- Application I/O Interface.
- I/O Scheduling: Buffering, Caching, Spooling and Device Reservation, Error Handling, Protection.
In the exam, CPU scheduling algorithm, semaphores algorithm, Process Creating and Banker’s Algorithm are checked. I think I did not write the correct semaphore algorithm since the question is a new situation instead of a classical example from the book.
In the oral exam, I zoom with three professors each covers one course. I am not sure whether they try to encourage me or not. While all of them told me that I did a great job in the writing exam.
Most of the questions originate from the exam questions. And they will check some related ideas and concepts during the process. Since I have reviewed all the related materials, the question is not very hard. If I cannot give the answers they want, they will hint me until I give the correct answer.
After all of the things, I finish my Preliminary Exam. Hope everything goes well. Cross fingers.