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

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

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):

  1. 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.

  2. Pass a written exam at the end of the semester. I will offer the exam at these dates and times:

  1. 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 working version of your project by Sunday, February 1.

  2. 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:

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.