NPRG031 Programming II (summer 2017-8)

Instructor: Adam Dingle

Programming II is a fast-paced course that will build on our knowledge from Programming I. The course has several goals:

We will learn the fundamentals of the C# language. We’ll study a number of features that are shared by C# and many other modern programming languages, such as classes, inheritance, interfaces, generics, exceptions, and lambda expressions. We will also study the C# collection class hierarchy and will learn to build our own collection classes.

We will not attempt to cover every feature of C# 7 or go deeply into its class library; for that, you can take NPRG035 C# Language and .NET Framework, offered in the winter term.
We’ll study various algorithms, data structures and programming techniques including hash tables, dynamic programming, recursive-descent parsing, informed (heuristic) searching and game-playing algorithms.
We’ll learn how to build larger programs. We will discuss basic principles of object-oriented design. Toward the end of the semester, we’ll look at how to build programs in various practical domains and will work through some extended examples. One such domain will be graphical user interfaces. Others may include network, database and/or game programming depending on how much time we have and on students’ interests.

Lectures and other meetings

The weekly lecture for this class takes place every Tuesday from 10:40 – 12:10 in room S11. The first lecture will be on Tuesday, February 20.
The weekly tutorial ("cvičení") immediately follows the lecture every Tuesday from 12:20 – 13:50 in the laboratory SW2.
I will also hold two mentoring sessions every week where we will work through additional exercises together. During the exam period, these sessions will take place every Wednesday from 14:00 – 16:00 and every Friday from 14:00 – 16:00 in room S510.

Requirements

To successfully complete this class, you must:

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. You will need to earn at least 70% of the possible points in ReCodEx.
Write a program in C# as a semester project. Your program should accomplish something that is interesting, cool, or fun and should be more substantial than your semester project for Programming I. A typical project for Programming II might be 500+ lines long. Here are some project ideas. Please send me a one-paragraph project proposal by Friday May 4^th. If at all possible, send me an implementation that is pretty much complete by Friday June 15th, so that there will be time to make any necessary changes. The deadline for submitting the final version of your project is Wednesday June 27th.
Take an exam at the end of the semester.
Regularly attend the lectures and tutorials and participate in class.

Textbooks

Michaelis and Lippert, Essential C# 6.0 (Addison-Wesley, 2016).
Weisfeld, The Object-Oriented Thought Process, 4^th Edition (Addison-Wesley, 2013).

You can purchase these books in PDF format via the links above.

Resources

Syllabus

This is a rough plan for the sequence of topics we will cover in this class. It will probably evolve as the semester goes on.

Feb 20: Local variables and assignment. Integer types, bool, char, string. Floating-point and decimal types. Arithmetic and Boolean operators. Compound assignment operators. String interpolation. Flow control: if, while, do/while. Accessing methods and properties in the base class library.
Feb 27 (tutorial notes) (exercises): Variable scope. More flow control: for, foreach, break, continue, switch, goto. Implicit and explicit type conversions. Writing static methods. Parameters and arguments. The return statement. Expression-bodied methods. Arrays. The 'new' operator. Multidimensional and jagged arrays. Calling constructors and operators in the base class library. The 'using' directive. File I/O.
Mar 6 (lecture notes) (lecture/tutorial examples) (exercises): Verbatim strings. Format strings. The conditional operator (?:). Reference and output parameters. Out variables. TryParse. Parameter arrays. Overloaded methods. Value and reference types. Null. Encapsulation via abstract data types. Defining classes and instance methods. The 'this' keyword. 'public' and 'private' access modifiers. Defining constructors. Default constructors. Overloading constructors. Constructor chaining. Overriding ToString().
Mar 13 (lecture notes) (lecture/tutorial examples) (exercises): Increment and decrement operators. Equality. Passing reference types by value and reference. Nullable types and conversions. Null-coalescing (??) and null-conditional (?.) operators. Enums. Static fields. Static constructors. Static classes. Defining properties. Indexers. Operator overloading. Resizable arrays. Linked data structures.
Mar 20 (lecture notes) (lecture/tutorial examples) (exercises): Assignment expressions. The 'is' operator. Polymorphism. Interfaces. Casting between base and derived types. The 'as' operator. Interface inheritance. Multiple interface inheritance. Explicit and implicit member implementation. Implementation inheritance. Virtual methods. The 'override' modifier. Calling base class methods. Defining structs. Streams.
Mar 27 (lecture notes) (lecture/tutorial examples) (exercises): Lifted operators. Readonly fields. Single and multiple inheritance. Calling base class constructors. The 'protected' access modifier. Abstract classes. Sealed classes and methods. The System.Object class. Inheritance versus containment. Model-view separation. Inheritance in the standard library. Algebraic data types.
Apr 3 (lecture notes) (lecture/tutorial examples) (exercises): Garbage collection. Exceptions. throw, try/catch/finally. Hash tables with chaining. Modulus as a hash function.
Apr 10 (lecture notes) (exercises): The Equals() method. Overriding Equals() and GetHashCode(). Generic methods. Generic classes and interfaces. The 'default' operator. Multiple type parameters. Generic constraints. Comparable objects. Comparers. Enumerable objects and enumerators. Collection interfaces and classes. Lists, dictionaries, stacks, queues.
Apr 17 (lecture notes) (tutorial examples) (exercises): Implicitly typed variables. Extension methods. Delegate types. Events. Programming graphical interfaces. The GTK# toolkit. Windows and widgets. Buttons and text boxes. Drawing with Cairo. Handling mouse and keyboard events. Transformations in Cairo. Timers.
Apr 24 (lecture notes) (exercises): Optional parameters. Named arguments. Covariance. Array covariance. Nested methods. Lambda expressions. Statement lambdas, expression lambdas. Outer variables. Functions as return values. Higher-order functions (map, filter, reduce) on arrays. Library functions on enumerations.
May 1: No lecture (state holiday).
May 8: No lecture (state holiday).
May 15 (lecture notes) (exercises): Iterators. Dynamic programming, with top-down and bottom-up approaches. Subproblem graphs. Rod cutting. Longest common subsequence.
May 22 (lecture notes) (exercises): More higher-order functions on sequences. Recursion with iterators. Game playing. The minimax algorithm. Alpha-beta pruning. Evaluation functions and cutoff tests. More dynamic programming. Solving problems using depth-first and breadth-first search.