CS61A: The Structure and Interpretation of Computer Programs

This course focused mainly on Python, covering computing paradigms like recursion and object-oriented programming, data structures like linked lists and trees, and some more advanced topics, including iterators and streams. It also covered functional programming and relevant topics, such as tail calls, by introducing us to Scheme, a derivative of Lisp. Finally, it exposed us to declarative programming by discussing SQL tables, joins, and recursive queries in SQLite.

MATH 54: Linear Algebra and Differential Equations

The first half of MATH 54 introduced us to fundamental but crucial linear algebra topics, including linear systems, linear combinations, independence, and transformations, vector spaces and bases, and eigenvector/values. In the second half, we moved on to ordinary differential equations of second order and higher and partial differential equations, which were much more complex and involved Fourier sine and cosine series.

CS61B: Data Structures and Advanced Programming

In this course, with Java as our tool, we intensively analyzed numerous data structures, including singly and doubly linked lists, array lists, hash tables, binary search trees (both simple and left-leaning red-and-black trees), queues/stacks, heaps, and tries. For each data structure, we studied its advantages and disadvantages in terms of runtime and its methods of implementation. We also went over crucial algorithms that used these structures, the most notable probably being sorting methods like mergesort, quicksort, and radix sort. We finished the year by focusing on graph theory algorithms, like depth-first search, breadth-first search, Dijkstra's algorithm, and Prim's algorithm. Some projects we completed included our own local version control system and an autocomplete program that generated and manipulated a trie from an inputted dictionary.

CS70: Discrete Mathematics and Probability Theory

This was my hardest but most interesting class this semester! In the first half, we focused on logic, studying propositions, quantifiers, proof techniques, particularly weak and strong induction, and graph theory, including Eulerian tours and hypercubes. We also covered numerous topics relevant to computing, such as RSA security and its implementation involving an exponential bijection dependent on modular arithmetic, polynomials and their roles in secret-sharing and error-correcting, and uncomputable problems, like the famous Halting problem. We moved on to discrete probability in the second half of the course, starting at basic counting techniques and conditional probability and moving on to advanced topics, like random variables, Bayes' rule, Chebyshev's inequality, and several significant distributions, including binomial, geometric (exponential in continuous probability), Poisson, and normal.

CS61C: Machine Structures

In contrast to 61A and 61B, CS61C focused on hardware as well as software. The course began with an intro to C; we studied topics like pointers and memory allocation and wrote a version control system in C. We then dove one level deeper into assembly language, using the MIPS assembly language as our learning tool. We not only programmed in MIPS assembly but also studied in depth the different instruction types (R-type, I-type, J-type) of a 32-bit MIPS machine and the diverse functionalities of the compiler, assembler, linker, and loader. Next, we focused on the actual computer hardware: the datapath and the control. Once again using the MIPS ISA, we learned the limitations of a single-cycle datapath and the benefits--but also resulting hazards--of a pipelined datapath with greater throughput. The course also strongly emphasized the topic of caches; we went over different types of caches, from direct-mapped to fully associative, and spent a great deal of time calculating hit/miss rates for sample code. After caches, we focused on techniques of parallelism, from SIMD vectorized operations and SSE intrinsics to MIMD, where we learned how to effectively use multiple threads with OpenMP in C to obtain unparalleled (haha) speedups, all the while being aware of complications resulting from data races and cache coherency. We also went over MapReduce and WSCs as prime examples of parallelism on a much larger scale. Finally, we discussed some other topics to a lesser degree, such as virtual memory and TLBs, Hamming Code Single Error Correction, and levels of RAID as an efficient organizational schema for secondary memory. Some projects we worked on over the semester include building our own assembler and linker in C and MIPS, building our own datapath + control in Logisim, and running a version of PageRank using MapReduce on Amazon's EC2 servers.

CS170: Efficient Algorithms and Intractable Problems

Another very tough but very interesting and useful class. We ended up going over numerous useful problem-solving techniques throughout the semester, and I definitely think that my ability to analyze a problem and devise algorithms has improved as a result of this class's extremely challenging homework problems. We began by going over divide-and-conquer techniques. We then moved on to graph theory, covering basic depth-first, breadth-first search, and DAG linearization. We then went over shortest-path algorithms like Dijkstra's and Bellman-Ford (for the presence of negative edges). After extensive graph theory, we focused on greedy algorithms like Kruskal's, Prim's, and Huffman encoding.

Next came two heavyweights of algorithmic design: dynamic and linear programming. I absolutely enjoyed dynamic programming because it is able to solve in polynomial time problems that seem, at first glance, tremendously difficult. I loved discovering the recurrence relation for a problem that told me the order in which to solve my subproblems because they were often so simply elegant yet so very powerful. Some particular problems discussed in class were edit distance and the Floyd-Warshall algorithm, used to find the shortest paths between all pairs of points in a graph. Linear programming also came across as extremely powerful. We discussed flow networks, the Ford-Fulkerson algorithm used to find the max flow, and reducing any circuit, and thus any polynomial-time algorithm, to a linear program.

For our last topic, we covered intractable, NP-complete problems, such as the infamous Traveling Salesman Problem, the satisfiability problem, and the set cover problem. We studied reductions and tackled many questions where we had to reduce an NP-complete problem A to a problem B to prove that B was NP-hard. We also went over a couple approximation algorithms for certain NP-complete problems. In fact, one of our final assignments was a coding project where we had to devise approximation algorithms for a given NP-hard problem, Maximum Acyclic Subgraph (given a directed graph, find the least number of edges to remove that will result in no cycles). Overall a very useful class and a great introduction to theoretical computer science.

CS186: Introduction to Database Systems

This course was very comprehensive in its coverage of database systems; we moved from the top layers of conceptual schema design, SQL as a declarative language, and query optimization all the way down to the physical design choices and buffer management strategies behind the scenes. We began the year by discussing external sorting and external hashing as methods to sort/hash data that was too large to fit in memory while minimizing I/O cost. After a subsequent period of focus on the SQL declarative language, we tackled physical database design. We first covered buffer management and page replacement policies, like LRU, MRU, and clock replacement. Finally, we went over indexes as solutions for fast lookup by key. We discussed the tradeoffs between ISAM and B+-Trees, insertion and bulk loading on B+-Trees, and the important differences between clustered and unclustered trees.

After physical design, we moved up a level to query optimization. We learned how to analyze the cost of different join methods, such as page-oriented and block-oriented nested loop joins, index nested loop joins, sort-merge joins, and hash joins. We then optimized query plans through the System R model of cost estimation and dynamic programming, focusing on left-deep plans to minimize the need for materialization of our joins.

Next, we moved on to concurrency control and recovery. We discussed the meaning of ACID transactions and learned to associate atomic and isolated transactions with serializable scheduling of transactions. We used 2-phase locking to guarantee conflict serializability and learned to detect and avoid deadlock situations among transactions. For recovery after a crash, we utilized the steal, no-force ARIES protocol with write-ahead logging, redoing all updates up until the time of the crash and then undoing the updates of all non-committed transactions.

In the last part of the course, we moved to an even higher levels and studied conceptual database design with entity-relationship models. With the help of entity-relationship diagrams, we designed systems with many-to-many, one-to-one, and many-to-one relationships. We next learned how to refine database designs and minimize redundancy by taking advantage of functional dependencies and normalization.

Projects in this class often involved using Pyspark for big data processing on RDDs. Some interesting assignments we had included coding our own strict 2-phase locking system and implementing K-means clustering through Pyspark to group together committee locations of the 2016 presidential candidates.

CS188: Introduction to Artificial Intelligence

I'm glad I took this course because it introduced me to many stimulating and unfamiliar topics in AI. We started off with basic concepts, such as state spaces, search algorithms, constraint satisfaction problems (solved with arc consistency techniques), and minimax/expectimax game trees (optimized with alpha-beta pruning). We then moved on to learn about Markov Decision Processes and, more importantly, reinforcement learning, where the agent learns about its environment online rather than offline. We practiced techniques like Q-learning to extract the optimal policy for an agent in a particular environment. (Personally, this section of reinforcement learning was my favorite part of the course.)

In the second half of the course, we moved on to probability. We learned about conditional probability and Bayes Nets, and how these directed acyclic graphs could be used to represent the joint probability distribution of numerous random variables. We also practiced inference-- making queries about the probability of certain variables given some evidence and some hidden variables--through variable elimination as an exact method and sampling techniques as approximate methods. Next, we covered Markov chains and hidden Markov models as representations of how the hidden state of an environment could be tracked with a transition model and observations at each time step. We ended the course with an introduction to machine learning and some of its fundamental components, including perceptrons to classify training data, multi-layer neural networks for deep learning of features, and gradient descent on the parameters of our model to minimize our training loss.

CS162: Operating Systems

An incredibly important class for me. It broke down numerous abstractions that I had just been taking for granted up to now, like how a machine could run simultaneous applications or how a filesystem worked. We started off by covering OS fundamentals like kernel syscalls, threads, processes, thread scheduling, and synchronization tools like semaphores, locks, and monitors. We then dove into virtual memory, caching, and demand paging as ways that processes could have separate address spaces and be given the illusion of infinite memory. After virtual memory, we transitioned to file systems, looking at several case studies like the simple FAT filesystem, the UNIX FFS, and the Windows NFS and the unique implementation details for each one. Finally, we ended the semester with a focus on distributed file systems, networks (with an emphasis on the TCP transport layer), and security (symmetric/asymmetric key encryption, integrity hashes, and certificates).

The homeworks assignments were generally more interesting than typical CS assignments. They included writing your own shell, your own basic HTTP server, and your own malloc and free programs. The bulk of the course's work, however, were in its three projects. We worked in project groups of 4 to design our own (simplified) Operating System called PintOS. In the first project, we implemented kernel threads, thread scheduling, and synchronization variables. The second project focused on supporting user programs and corresponding syscalls, like fork, exec, wait, and exit. Finally, the third and most challenging project had us create our own filesystem, complete with a buffer cache, extensible files, and directory support. All projects and homeworks were written in C.

CS176: Algorithms for Computational Biology

I took this course after liking CS170 so much and enjoyed another stimulating semester of problem-solving. It was very interesting to learn about algorithms that had applications beyond the scope of pure CS and the tech industry, some of which were actually used daily in the professor's computational biology lab.

The course's first major section was on exact and inexact string matching. We covered algorithms like the Z-algorithm and crucial data structures like suffix trees and suffix arrays that could be used to solve the problem of finding all instances of a pattern in a given reference string in linear time. In my opinion, these applications had the most overlap between computational biology and software engineering in the tech industry. We then went over the Burrows-Wheeler Transform as a way to more compactly store the reference string via Huffman encoding to allow for numerous efficient lookups. Finally, we ended the section by covering inexact matching, where dynamic programming algorithms like Needleman-Wunsch (similar to the edit distance algorithm) became essential.

Our next major section covered phylogenetic trees, binary trees used to depict similarities and potential ancestor chains among a set of taxa as accurately as possible (these taxa could be different species, different genes/proteins, etc.). We covered various topics, like the difference between distance-based and parsimony-based trees and how to determine whether we could construct a tree with the maximum possible degree of accuracy in representing the differences between the taxa. In the last section of the class, we dealt with probability. We used homogeneous Markov chains as a way of calculating the likelihood of a phylogenetic tree, using transition probabilities for parent nodes in the tree transitioning to the state of their children. Lastly, we went in depth with HMM's, looking at how to calculate the likelihood of parameters given only observations with the forward algorithm, determine the most likely sequence of hidden states given observations and parameters with the Viterbi algorithm, and find the most likely set of parameters for a set of observations with the expectation-maximization Baum-Welch algorithm.

CS189: Machine Learning

A great introduction to the field of machine learning, which is becoming so ubiquitously used in today's technology. It was easily the most math-heavy CS course I have taken, and it illustrated that linear algebra and statistics are extremely useful for understanding machine learning models in depth.

We first covered linear classifiers, starting with perceptrons and support vector machines and moving on to study a generative approach to classification with Gaussian discriminant analysis. Next, we moved on to regression, tackling linear and logistic regression, as well as ridge regression and Lasso (using regularization to reduce overfitting). We also went over statistical derivations of these regression models and discussed the important bias-variance tradeoff of any model. Along the way, we discussed optimization methods, such as gradient descent and maximum likelihood estimation, and other topics like feature lifting and kernels, which could be used to train from an amplified number of features without incurring an additional performance cost.

In the second half of the course, we covered decision trees, which provided a very intuitive method of classification. And of course, we extensively studied neural networks, going over both their fundamental structure and how it could be tweaked and extended to improve training speeds (avoiding the halting gradient problem), reduce overfitting, and find better local minima. In the course's last segment, we studied unsupervised learning. Topics included using principal components analysis to reduce dimensionality without a large loss in information, employing k-means and spectral graph clustering to group points in space or vertices in a graph, and using latent factor analysis and the singular value decomposition of a matrix to build recommender systems.

Homework assignments were generally very math- or coding-intensive. The most interesting ones required us to build certain machine learning models from scratch. For example, we built our own neural nets to classify the MNIST handwritten digit data set, and we used SVD to build a basic joke recommender system. We submitted our code to Kaggle competitions, where our models would run on test data sets and needed to get above a baseline accuracy to get full credit.

CS161: Computer Security

A fascinating course that enlightened me about the capabilities of cyberattackers, the types of vulnerabilities that they exploit, and the defenses that are available.

In the first part of the course, we focused on buffer overflow attacks that could lead to malicious code injection, as well as several common defenses to mitigate these vulnerabilities, like stack canaries and address space layout randomization. We also heavily covered web attacks, particularly SQL injection, CSRF attacks, and cross-site scripting attacks (both persistent and reflective). Some important defenses/web policies we considered were the same-origin policy (and how the aforementioned attacks circumvented it), the OWASP guidelines on properly sanitizing user inputs, Content Security Policy headers for preventing injection of JS scripts from third parties, and prepared statements for protecting against SQL injection.

Our next module was cryptography. We focused on AES-128 as a good symmetric-key block cipher and studied several modes, like CBC and CTR, for encrypting arbitrarily long messages. We also discussed asymmetric-key cryptography, especially RSA. Furthermore, we went over techniques to guarantee integrity and authenticity, such as cryptographically secure hash functions, message authentication codes (MACs), and digital signatures, which could be used by trusted certificate authorities to vouch for a party's public key.

Finally, we went over internet security. The topics we covered were numerous and diverse, ranging from attacks on the DHCP protocol to impersonate the victim's primary DNS server to an in-depth look into how DNSSEC could prevent dangerous DNS cache poisoning attacks from occurring. Probably one of the most important topics we studied was SSL/TLS. We learned not only about how the TLS handshake worked and was immune to any man-in-the-middle attacks but also about the implications of trusting seemingly obscure certificate authorities to sign cert requests discreetly and protect their private key from compromise. Our last topics were on intrusion detection techniques (signatures, behavioral detection, etc.) and on malware, viruses, and worms.

Projects for this course were fun and challenging. I got the chance to both build secure systems and attack mock vulnerable systems, which made me and my project partner a lot more conscious about looking for exploits in our and in other people's code. Some project tasks included finding holes in sample code that would allow you to inject code through a buffer overflow, conducting MITM attacks on a TLS connection by taking advantage of a given certificate authority key, and building a file system that could protect the contents and integrity of a client's files from a malicious file server. I coded primarily in C and Python for these projects.