CS165 Self-Evaluation

Do you have what it takes ?
  1. Introduction

    This is a discussion to help you better understand the scope of CS165 and whether you have the necessary background to successfully attend the course.

    If you do not feel comfortable with all the material discussed here this does not necessarily mean that you cannot follow the course. But it does give you an indication of how much extra work you will have to do to get familiar with concepts and tools that are essential for the course.

    The course is designed to be as self-contained as possible: during the semester we will provide you with several resources to build your systems knowledge and skills and there is an extensive array of sections, labs and office hours to help you build the necessary background.

    In addition, here we provide guidelines on how you may prepare for the course prior to the semester or during the early semester weeks with suggestions about tools that you can start exploring, as well as a specifically designed programming task, Project 0, that will help you develop (or refresh) basic skills at designing and implementing data structures and algorithms. These skills will be essential for following the class.

  2. Relevant Areas

    CS165 is a heavy systems class. It has a hefty semester-long project that will stress your abilities in the following areas:

    1. C programming
    2. Data structures
    3. Algorithms
    4. Computer architecture

    These areas are essential for CS165 and some basic familiarity with all these areas is advised so you can keep up.


    C Programming

    The class uses the C language. This is because a low-level language is required to design and build efficient systems as we need to have full control of how we utilize memory and computational resources.

    The basic concepts of the C language are quite similar with other programming languages. Once you know how to write for loops and if statements you are good to go and then learning a new language is primarily about getting familiar with the syntax and its structure which is typically a trivial task.

    You can easily find several detailed tutorials online to get you started with basic C concepts.

    Here are some areas to focus on:

    • C syntax including pointer arithmetic/manipulation
    • Memory management (malloc/free)
    • File I/O
    • Recursion
    • Structs
    • Header files
    • pthreads (concurrency)
    • Synchronization Primitives (mutexes, condition variables, etc.)

    If you have previous experience with other languages but not with C, then most likely the new thing you need to get familiar with is pointer and memory management. Here is a nice tutorial on that http://pw1.netcom.com/~tjensen/ptr/pointers.htm.

    If you do not have any familiarity with programming before, then you should not take CS165.


    Data Structures

    Data structures are essential in data systems. They drive the physical organization of data and the access methods we use to retrieve data. You will design several simple and complex data structures during CS165 such as arrays, lists, and trees.

    There are two aspects when it comes to data structures. The first one has to do with the abstract design of data structures and their properties. The second one has to do with their proper implementation.

    If you have done C programming in the past, it is likely that you have implemented a few data structures. If not, then it is advisable that you spend a few days prior to class to experiment with some basic concepts. For example, an excellent exercise is to create a simple linked list. You can find numerous detailed tutorials online: search for “linked list C”. If you go through such a task then you would have developed enough C skills as well.

    Also check the Project 0 that we provide which walks you though such a programming task.


    Algorithms

    Algorithm design is essential in any area of computer science. You will design several algorithms during the semester for your data system and we will discuss several algorithms in class.

    A basic familiarity with algorithm design at the level of an introductory CS class is fundamental. For example, do you have trouble understanding how a basic sort algorithm (e.g., quicksort) works or how a basic tree traversal happens? If yes, it is advisable that you refresh your basic algorithms skills. The two examples mentioned here can be excellent starting points and you can easily find several resources online. In addition, the simple exercise suggested in the previous section about creating a linked list will force you to think about the proper algorithms to manipulate the linked list efficiently such as insert new items, remove items etc. So it is an excellent exercise for that as well.


    Computer Architecture

    Modern systems are designed in such as way that they utilize modern hardware properties. This is essential in order to get the maximum efficiency (speed but also energy consumption).

    CS165 teaches you about modern systems tailored for modern hardware and so it requires good understanding of modern computer architecture. We will give enough background during class, office hours and sections but some initial familiarity will certainly cut down your workload during the semester.

    For example, if you are not aware of the basic properties of a multi-core CPU, memory, disk or a cache then you it is advisable that you spend an evening or two browsing some basic tutorials.

  3. Student Categories

    Here we categorize students based on their past experience and give you hints regarding how fit you are for CS165.

    Case 1 - Basic Computer Science: The minimum and hard requirement is that you have taken at least an introductory computer science class such as CS50 or you otherwise have basic knowledge of computer science. If you fit in this category, you should carefully go through the discussion in this self-test and the class material to see that you understand the scope of the class and the material you would have to cover. Many students in the past successfully took CS165 having taken only a basic computer science course before so this is perfectly doable and we are here to help you with anything you need.

    Case 2 - Basic Systems: The normal case is that you have taken an introductory systems class before such as CS61. If you fit in this category, then this means that you already know a bit more about the 4 areas of the class than what a standard computer science introductory class gives you. You have all the necessary background to follow CS165. It is still a good idea to carefully go through the material of CS165, the self-test, and to do the Project 0 to identify areas you might want to refresh prior to class.

    Case 3 - Prior Systems Experience: The ideal case is that you have taken another heavy systems class before, such as CS161. If you are in this category then this means that you are very comfortable with systems design and the 4 areas of the class. You will be OK in CS165.

    Case 4 - Familiarity with (nearly) all Areas: Another category includes students that do not have any systems experience but do have good understanding and knowledge of all or nearly all areas of the class. If you fall in this category you will be OK in CS165. It is advisable that you carefully go through the self-test and the class material to see if there is an area you would like to work on prior to class but you will have time to do so during the semester as well.

  4. Tools

    We are going to be using several tools during the semester to build and debug modern data systems. Learning tools is typically just a matter of time and practice. We will provide you with enough sections and office hours to train you on the basics of these tools. If you have time prior to the semester you can spend some time getting familiar with the following tools:

    gcc compiler to compile C (gcc.gnu.org)
    gdb to debug your system (www.gnu.org/software/gdb)
    valgrind to do memory profiling (valgrind.org)
    perf for all kinds of monitoring and performance counters (perf.wiki.kernel.org)

    git for version control (git-scm.com)

    For example, you may do the linked list exercise mentioned before and Project 0 using gcc to compile your C program, gdb to debug and valgrind and perf to do profiling and performance analysis. You can find extensive tutorials online for all these tools.

Download Project 0 description as a pdf.
Get the Project 0 skeleton code from this repository.
Watch the Project 0 video section here.