NPRG030 Programming I (winter 2018-9)

Instructor: Adam Dingle

This course is a fast-paced introduction to programming and to data structures and algorithms, with a strong emphasis on learning to write working code. It assumes no previous programming experience.

The course has two major goals.

First, we will learn the Pascal programming language, mostly in the first six weeks of the course. Specifically, we will use the dialect of Pascal understood by the Free Pascal compiler.

Second, we will study fundamental data structures and algorithms and learn to analyze their run-time efficiency.

Throughout the course students will complete many programming exercises in Pascal, both to implement the algorithms we study and also to solve a wide variety of other programming problems.

Lectures and other meetings

The weekly lecture for this class takes place every Monday from 9:50 - 12:05 in room S11. The first lecture will be on Monday, October 1.
There is also a weekly lab ("cvičení") every Monday from 14:00 – 15:30 in the laboratory SW1. In the lab we will solve various programming problems together. Each student will sit at a workstation where they can write code during the discussion.

If you want more programming practice, here are two more opportunities:

I teach a weekly practice session every Wednesday from 9:00 – 10:30 in the laboratory SU1. This is a separate class that you can register for (NMIN161 – Practical Course in Programming for Beginners) and is worth 1 credit.
I also lead a weekly mentoring session where we can work through practice problems and can also discuss topics of interest from your other computer science classes. The mentoring session happens every Friday from 13:00 – 14:30 in room S510. Mentoring sessions will continue through the exam period until Friday, February 8.

Requirements

This is a pass/fail course: you will not receive a numeric grade.

To pass this class, you must fulfill the following requirements by Friday, February 15, 2019 (the end of the exam period):

Complete a number of programming exercises through the semester. I will assign these exercises weekly, and you can submit your solutions to the ReCodEx automated grading system. To pass, you will need to earn at least 160/240 points (i.e. 2/3 of possible points) on these exercises.
Pass a written exam at the end of the semester. I will offer the exam at these dates and times:

10:00 - 12:00 on Mon Jan 21 in S11
10:00 - 12:00 on Mon Jan 28 in S7 (note room change!)
10:00 - 12:00 on Mon Feb 4 in S11
10:00 - 12:00 on Mon Feb 11 in S11

Write a program in Pascal as a semester project. Your program should accomplish something that is interesting, cool, or fun and can be 100-300 lines long, or longer if you like. Here are some project ideas. Please send me a 1-paragraph project proposal by Sunday, January 6. Send me a first working version of your project by Sunday, February 3. In writing your project, please follow the guidelines for writing good code that we learned in this course.
Regularly attend the lectures and tutorials and participate in class.

Textbooks

I will publish lecture notes each week that review the information covered in the lectures. For our discussions about algorithms, you may optionally also read selected chapters from the following textbook:

Cormen, Leiserson et al, Introduction to Algorithms, Second Edition (MIT Press, 2001)

There are many copies of this book in the MFF library on the first floor.

Resources

Syllabus

This is a rough map of the ground we plan to cover in this class, with plenty of interesting twists and turns along the way.

October 1 (lecture notes) (exercises): Course overview. Computers, programs and programming. Powers of two. Bits and bytes. The Pascal language. Primitive data types: integer, boolean, real, char, string. Variables, constants. Assignment statements. Comments. Console input/output. Arithmetic and comparison operators. The 'if' and 'for' statements.
October 8 (lecture notes) (exercises): Boolean operators. Looping with 'while' and 'repeat'. Calling standard library functions. The int64 type. The 'break' and 'exit' statements. Primality testing using trial division. A number-guessing game.
October 15 (lecture notes) (exercises): Dividing an integer into digits. Accessing characters in a string. Static and dynamic arrays. Integer factorization.
October 22 (lecture notes) (exercises): Text files. The for...in statement. Multidimensional arrays. Functions and procedures, global and local variables. Passing parameters by value and reference. Bubble sort. Debugging.
October 29 (lecture notes) (exercises): Type declarations. Open array parameters. Const parameters. Binary search for values. Big-O notation and running time analysis. Div and mod with negative numbers. Splitting into digits from left to right.
November 5 (lecture notes) (exercises): += and related assignment operators. Records. Binary search for boundaries. Insertion sort. Non-decimal bases.
November 12 (lecture notes) (exercises): Explicit range types. The 'case' statement. Enumerated data types. Greatest common divisor. Euclid's algorithm. Recursion.
November 19 (lecture notes) (exercises): Partial arrays. Recursion with partial arrays. Sorting with a custom ordering. Merging sorted arrays. Mergesort. Stacks.
November 26 (lecture notes) (exercises): Units. Pointers and dynamic memory allocation. Linked lists. Least common multiple.
December 3 (lecture notes) (exercises): Out parameters. Queues. Sets. Binary trees. Binary search trees.
December 10 (lecture notes) (exercises): Nested functions. Maps. Quicksort. Graph representations. Depth-first search, breadth-first search.
December 17 (lecture notes) (exercises): Combinatorial search with recursion. Prefix, infix and postfix expressions. The Tower of Hanoi.
December 24, 31: No lecture (winter vacation).
January 7 (lecture notes) (exercises): The sieve of Eratosthenes. Priority queues. Binary heaps. Heapsort. Context-free grammars. Parsing arithmetic expressions.