Lectures: Wednesday, 12:20, S5 (Pavel Ježek)
Labs: Monday, 10:40, SW2 (Filip Kliber)
Page in SIS: NPRG035
Grading: Credit and exam
Table of contents
- Lectures outline
- Practicals outline
- Information about the Exam
- Requirements for the Credit
- Acknowledgement of requirements from past years
[in Czech] Zde jsou informace pro studenty anglické paralelky předmětu Programování v jazyce C#. Pro českou si v záhlaví stránky přepněte jazyk do češtiny.
Lectures outline
1. Lecture
- Introduction to course, exam
- Differences in memory representation of variables in Python, C++ and C# languages
- Differences between reference and value types, passing arguments by values
- Memory overhead of reference types, a
Type
class record (class)
,record struct
Materials
2. Lecture
- Reminder of differences between reference and value types, specified at the point of type declaration
- Examples of typical reference, resp. typical value types
- Implicitly typed variables (
var
),new
without the name of the type in context where it makes sense (parameter, declaration) - Fields vs. properties in types,
readonly
- Automatically implemented properties
- Allocation on GC heap, nulling of memory, constructors, initializers
init
setters for properties (C#9), keywordrequired
(C#11)
Materials
- Slidy
- 02.0a-PersonClassColorStruct.zip
- 02.0b-PersonStructColorClass.zip
- 02.1-PropertiesVsFieldsSyntax.zip
- 02.2-PersonConstruction.zip
3. Lecture
- Reminder of nullable value types
null
in runtime of .NET (CLR) and accessingnull
leading toNullReferenceException
- Nullable reference types (C#8)
- Duck typing in Python, dynamically typed languages
- Interface in C#, interface table
I
within a typeA : I
and finding a method by tracking several pointers in situation likeI i = new A(); i.m1();
- Hiding base methods via
new
keyword and finding a correct method that will be called - The
is
operator andInvalidCastException
, including the more recent variantvariable is Type newVariable
- Properties (not fields) as part of the contract in interface
Materials
- 03.1-TraditionalCSharpNullable.zip
- 03.2-NullableReferenceTypes.zip
- 03.3-DuckPostPython.zip
- 03.4-InterfacesInClassHierarchy.zip
- 03.5-DuckPostCSharpContracts.zip
- 03.6-NamePropertyInDuckPostCSharpContracts.zip
Practicals outline
1. Practicals
- Introductory lecture, course requirements (also available on this very page)
- Recap of using the Visual Studio as IDE
- Creating new projects, structure of the project
- Configuration, Intellisense, Block selection, Documentation comments, Indentation
- Compilation, Running, Debugging (basics)
- Visual Studio extension adding a template for creating ReCodEx complying projects can be downloaded from here
- New homeworks Word Counting a Word Frequency
2. Practicals
- Reading words from file
- ✖
StreamReader.ReadToEnd
(problem with extremely large files) - ✖
StreamReader.ReadLine
(problem with extremely long lines) - ✔
StreamReader.Read
(by characters)- Returns an
int
(extra-1
in the range ofchar
for end of the file indication) - Conversion to
char
via standard casting(char)
, after== -1
check for end of the file.
- Returns an
- ✖
- Checking if the file exists, if it’s openable and readable only via exceptions from
StreamReader
methods.File.Exists
is insufficient when there are more processes on the system
- Problems with catching more generic exceptions (
catch (Exception)
hidesOutOfMemoryException
) - Frequency counting
SortedDictionary
vsDictionary
vsSortedList
vs Your own DataStructure- Depends a lot on the ratio of unique words to all words.
- Micro benchmark
- New assignment Block Justification
- One line might not fit into the memory anymore
3. Practicals
- Comments on some issues encountered in Text Justification assignment
diff
tool (Command Line)- Graphical: KDiff3, Visual Studio Code
- Testing of applications
- Integrated Testing
- UnitTesting (MSTest, xUnit, NUnit, MSDN tutorials (.NET Core))
- ArrangeActAssert
- Mock-ups
- WordReader example: ProgramTests with Mock-ups, WordReaderTests, Bundled in project for .NET Core 3.1
- New assignment Multifile Text Justification
- Extension of previous assignment
- 5 points only
- 5 extra points for reasonable UnitTests
- UnitTests submitted in separate file with everything commented (so that it’s not compiled)
4. Practicals
- Bad unit test design in form of integration tests (testing all possible combinations of method arguments in whole program instead of testing just by individual methods)
- Testing of the “left-overs” (glue-code)
- Method
Run
that can get modified arguments - Testing of
Console
via invokingRun(TextWriter)
(from Main asRun(Console.Out)
)
- Method
- Text Justification comments
- Basic version with private methods for printing justified text (impossible to unit test)
- Advanced version with
ILineJustifier
, that can be used in highlighting as well viaIStringWriter
, which are adaptor and wrapper design patterns.
- New assignment Bookstore eShop
- Design pattern ModelViewController (MVC) can be useful here
5. Practicals
- Last thing about Multifile text justification:
- Processing multiple files via factory design pattern
- Reference solution of the bookstore eShop assignment
- New assignment Huffman I
- It is mandatory to store the tree in the memory, solutions printing the tree on the file will not be accepted.
6. Practicals
- Comments for the Huffman I assignment
- Realizing the importance of performance of individual parts of the application (reading the file or building the tree)
- Differences between
BinaryReader
andFileStream
, internal implementation details, and potential improvement by using additional layer of buffering (of size 2n) - Approaches to counting frequencies:
Dictionary<byte, long>
vs.new long[256]
(int
is not large enough for 1TiB files) - Memory representation of
HuffmanTree
: straightforward or more object oriented approach - Building the tree:
PriorityQueue
(heap) vs. two simple queues (Queue
) for leaf nodes and inner nodes, or one sorted list with inserting nodes at correct place (semi insert sort) - Printing the tree: recursion vs. explicit
Stack
- Possible solution
- New assignment Huffman II
- Bit operation in C#: or
|
, and&
, xor^
, not~
, left shift<<
right shift>>
(>>
is dependant on the signedness of the type) BinaryWriter
BitConverter
,byte[] GetBytes(int)
,GetInt32(byte[])
, …
- Bit operation in C#: or
7. Practicals
- Comments on the Huffman II assignment
- Again, realizing the impact on the performance (reading the file vs. building a tree vs. reading the file again vs. writing into the file)
- How to generate the bit sequences
- ✖ Using
string
, e.g."1011" + "0"
, which does new memory allocation and has to copy the contents of both strings into a new one - ✖ Converting the
string
binary asConvert.ToByte("10110", 2)
is universal algorithm supporting more bases, while binary is natively supported by CPU.- Better would be to use Horner’s method and adding (
or
ing) the binary values.
- Better would be to use Horner’s method and adding (
- ✔ Using bit operations (or
|
, and&
, xor^
, not~
, left shift<<
right shift>>
)
- ✖ Using
- How to set n-th bit in
value
as 1? Asvalue | x
, where binary representation ofx
has all zeroes, expect for one1
at n-th position, which is 2 to the n-th power.- ✖
Math.Pow(2, x)
is again universal, supporting exponentiation of real numbers, contains a generic algorithm for exponentiation, not for just powers of two - ✔
1 << x
- ✖
- How to unset n-th bit (set it to 0) in
value
? Asvalue & x
, where binary representation ofx
has all ones, expect for one0
at n-th position, which is binary negation of 2 to the n-th power.value & ~(1 << n)
- It is a good idea to use some sort of cache for codes, so that we don’t have to traverse through the tree over and over
- Possible solution
- Difference between
byte[] BinaryReader.ReadBytes(int lenght)
andint FileStream.Read(byte[] buffer, int offset, int length)
, where the former has to allocate new buffer every time whereas the later can reuse the same buffer.
- Using
@
symbol before name makes it possible to refer to identifier which would be reserved word (e.g.int @while
, orvoid @else()
). verbatim identifier- Useful when interacting with a .NET language L that exports identifier with a name that would be a reserved word in C#, but is not in L.
- Using underscore in decimal constant allows visual separation of digits for the reader (e.g.
int price = 12_751;
, orulong bits = 0b10110010_10010101
). digit separator - Introduction to profilers in .NET for measuring the performance of the CPU
- Sampling
- Runs exactly the profiled program, and at regular intervals, stops the program and takes a sample — information about the instruction pointer, e.g. the exact location in the code where the program was stopped.
- Makes these samples into statistics with idea that recurring samples means that line of code takes more time
- Not able to take samples in kernel code (e.g. IO operation)
- Small overhead, imprecise, generates reasonable amount of statistics data.
- Instrumentation
- Modifies the existing program in a way that beginnings and ends of every function call the profiler code, which can measure exact time spent in the function
- These data are presented in exact manner
- Able to measure duration of calls to OS kernel (e.g. duration of IO operation)
- Big overhead, precise, generates massive amount of statistics data.
- Interpret those results with a care
- Sampling
- New bonus assignment Huffman III (deadline in summer semester)
- Reverse approach to Huffman II — Decompression
- Nothing new, thus not discussed on practicals and thus late deadline
- New regular assignment Excel
- Do not process the sheet on the fly, but load the sheet, evaluate the sheet and write it to the file
- Do not try to support evaluation of values in other types (e.g. in doubles)
- Do not try to support other formula types (e.g. functions, multiple operators)
- Basic solution will give only 80% (12/15 points), for 100% (15 points) an extension has to be developed as well
8. Practicals
- Extending the deadline for Excel assignment by one week
- Hints on how to solve the Excel assignment
- DO NOT evaluate the sheet on the fly. Load and parse the sheet first, then evaluate it, then print it out.
- Cells have different content (
13
,=A1+B2
,[]
, …) and so it is logical they would have different type in the object oriented approach - This automatically saves memory, because every cell stores just what it needs (e.g. the empty cell wouldn’t store any data at all)
- This also leads to nice design that is easily extendible. If we wanted advanced formulas, we would just introduce new type and the rest could stay the same.
- Also, the Sheet data structure shouldn’t be dependant on the format of the input file. If the input file changes (e.g. we’ll want to support Microsoft’s
.xls
format), we don’t want to change the data structures used to store the data. - Think about the overhead of data structures, e.g. think about the overhead of
Dictionary
inDictionary<string, Sheet>
(basically no overhead) andDictionary<string, int>
(hundreds of percents overhead) - Try to build up an example data by yourself, you can definitely write easy program that will produce complex excel sheet with thousands rows and evaluation of thousand steps
- Conditional compilation
- Two different sets of code in one file for two purposes (e.g. debugging and release)
#define IDENT
,#if IDENT
,#else
,#endif
(also defined in the project properties, depending on the configuration)#warning
,#error
- Task list in visual studio
- Special keywords in comments (
HACK
,TODO
) that are processed by the Visual Studio and shown in Task List window
- Special keywords in comments (
- Introduction to version control systems
- Archaic SVN with Local Working Directory (commit/update) Central Repository
- Modern Git/Hg with Local Working Directory (add/remove) Staging Area (commit/checkout) Local Repository (push/pull) Remote Repository
- Example of using Git with GUI tool (Tortoise Git) or directly from Visual Studio
- Other GUI tools: GitExtension (Windows, Git), SourceTree (Windows/Mac, Git/Hg)
- Using Git from command line (and more useful software for SW development) is taught at the Software Development Tools course.
- New bonus assignments (deadline first week of summer semester)
- Logic Circuit I, 30 points
- Logic Circuit II, 30 points
- Logic Circuit III, 40 points
- Assignments that are very easy algorithm-wise, but very hard design-wise. Reasoning about how to approach these assignments in OOP way is crucial!
- Example of simple logic circuit and simulation over specific input.
9. Practicals
- Excel Impossible
- Comments on the Excel assignment
- Difference between storing values as
int
s (1234
), orstring
s ("1234"
) in terms of memory consumption - Idea is to differentiate between cells with different content by different types
- Separation of Sheet parsing algorithm and individual algorithms for parsing cells
- Parsing of cell references
- ✔ Horner scheme
- ✖
int.Parse
; parses also-10
or00123
- ✖ Regular expressions; difficult to read, heavy in terms of time needed to parse the expression into automaton and match the string
- Possible solution
- Difference between storing values as
- New assignment Expression Evaluator
- Expression in prefix form should be parsed into some data structures and then evaluated and the result should be printed.
- Focus on extensibility in new operators, operators with higher arity (functions).
- Do not make it work with universal types (
double
,string
, complex number, fractions). Expression will always be integral (int
). - Use recursion for evaluation of the expression as it will lead to better design.
- 5 points for passing tests, additional 5 points for good design of the representation of the expression in the memory.
10. Practicals
- Comments on the Expression Evaluation I
- Representation of expression as a tree (leads to easy manipulation with sub-expressions; Abstract Syntax Tree)
- Usage of
sealed
andabstract
C# keywords as hints to other developers on what should be extended/instantiated as well as for minor optimizations. - Disadvantages of
Expression[] array
as a children nodes. Using explicit classes (BinaryOperator
, …) with given arity. - Concrete classes
PlusExpression
,MinusExpression
, … for separation of tree evaluation and node calculation. - Parsing of the input string via Stack of unprocessed expressions, which requires support in the
Operator
class asAddOperand
method (which doesn’t break immutability). - Disadvantages in using
switch (token)
for construction of individual operations. Resolution of this issue was not presented (see bonus below) - Possible Solution
- Explanation of Visitor design pattern.
- New assignment Expression evaluation II
- 5 base points for working solution
- 5 extra points for implementation of the Visitor design pattern for evaluation of expressions in real numbers (the original integer evaluation can be left as is)
- Bonus: 5 extra points for implementation of the parsing algorithm that can be taught how to parse new operators (provided by other developers) easily, without any need for
switch (operator)
construct.
11. Practicals
- Comments on the Expression Evaluation II
- Using a base interface for all visitors to allow more algorithms to be added
- Visit methods having concrete operators (
PlusExpression
, …) in order to get rid ofswitch (operator)
- Problems with returning value from
Visit
andAccept
methods sorted from worst to best:- ✖ Using
double
sinceint
can fit indouble
(not actually, andstring
won’t fit intodouble
anyway) - ✖ Using
object
as a return type. Problems with boxing and possibleInvalidCastException
at runtime - ✖ Using explicit stack instead of call stack to pass the return value, stored in the visitor
- ✖ Multiple visitor interfaces and multiple
Accept
methods with different return values - ✖ Single value stored in the algorithm shared when evaluating sub-expressions
- ✔ We will learn the best way to do that later
- ✖ Using
- Parsing bonus not presented. It is still possible to implement the bonus in next assignment and get points
- New assignment Expression evaluation III
- 5 base points for working solution
- 5 extra points for implementation of algorithms as visitors complying with these rules:
- Addition of new algorithm doesn’t modify the existing data structures
- Addition of new operator yields all existing algorithms not compilable
- Bonus: 5 extra points for implementation of the parsing algorithm that can be taught how to parse new operators (provided by other developers) easily, without any need for
switch (operator)
construct
Information about the Exam
Primary part of the exam consist of written part including around 6 to 8 questions (which might include sub-questions). Every question has a visible maximal amount of points that can be awarded for the question (=N
). For correct answer, the student will receive N
points for the question; for incomplete, but overall good answer (i.e. some part of the answer is missing or is incorrect), the student will receive 0.5 * N
points; in other cases, the student will receive 0
points (i.e. if the answer is missing completely or is mostly incorrect).
The student can receive up to 10
points from the Exam. The mapping between points and grade is as follows:
Points from the exam | Awarded grade |
---|---|
10 – 8.5 | 1 |
8 – 6.5 | 2 |
6 – 5 | 3 |
4.5 – 0 | 4 |
The written part of the exam takes up to 150 minutes (i.e. 20 minutes for each question, with 30 minutes extra time). After the written part, the oral part follows, where the examiner discusses the answers with the student, demands clarification when needed and asks complementary questions if deemed necessary — based on this, the final amount of points for each question is determined. The evaluation is always based on written part of the Exam, which means that student can’t be awarded with more than 0 points for a question without an answer.
For illustration, here follows a list of some exams from previous years:
- 1.2.2021 (PDF)
Requirements for the Credit
In order to receive the credit, it is necessary to fulfill three requirements:
1. Practical Test
Fully implement a simple task within a 3 hour time limit. Takes place during the examination period in computer lab. You have five attempts to complete the test in total, but you can attempt the test only three times during the winter (you can take other two in summer examination period).
2. Final Project
Deadlines:
- Specification: 7. 7. 2023
- Demonstration of the final (fully functional, according to the specification) version of the application, including both user and development documentation.
-
- deadline: 9. 8. 2023
-
- deadline: 8. 9. 2023
-
You can use single project to complete several courses about C# and .NET, if the project is complex enough:
- Requirements for NPRG035:
- Demonstrated before the 1. deadline: 30kB of source code written in the C# language
- Demonstrated after the 1. deadline: 45kB of source code written in the C# language
- Demonstrated after the 2. deadline: 60kB of source code written in the C# language
- Requirements for NPRG035 + NPRG038, Advanced .NET Programming II:
- Demonstrated before the 1. deadline: 45kB of source code written in the C# language
- Demonstrated after the 1. deadline: 60kB of source code written in the C# language
- Demonstrated after the 2. deadline: 90kB of source code written in the C# language
Source code is the code you (and only you) wrote in C# language. Comments are included, but everything has to be reasonable.
Final Project for Advanced C# Programming require additional (nontrivial) usage of features and techniques taught during lectures of that course.
If the application has nontrivial graphical interface, you can use it to get credit for Programming User Interfaces in .NET as well.
Please prepare few slides (talk) about your application’s main features, problems you faced and overall design overview.
3. Homeworks
There will be several small homeworks assigned during the semester. If you complete a homework you will get points (10p usually). You are required to obtain at least 80p from the homeworks. By having more points from homeworks, you can get some extra points to the exam test.
Points from HW | Bonus to the exam |
---|---|
100+ | +1.25 strong points |
120+ | +2 strong points |
150+ | +2 strong, +0.5 weak points |
200+ | +2 strong, +1 weak point |
Strong points only work during the first attempt on the exam. Weak points can not change the result of the exam from 4 to 3.
Homeworks will be assigned using the ReCodEx system. You will also submit your solutions to this system and it will be automatically graded. The usual deadline will be 7 days. You can also gain some extra points if your solution is well-designed, has relevant comments present or has other aesthetic features that the system can’t grade.
Note: Homeworks are strictly individual.
Acknowledgement of requirements from past years
If the student was enrolled in this course during the last academic year and fulfilled only some of the requirements for the credit, the teacher can, upon student’s request, acknowledge the fulfillment of requirement from the last year (attendance, homeworks, Practical Test or Final Project). The topic (specification) of Final Project does not need to be acknowledged by new teacher. If the student succeeded in the exam, but didn’t receive the credit, Pavel Ježek can, upon student’s request, acknowledge the result of the exam. This is a good will of teachers of this course and students can’t enforce this on study department!