CSF101 - Programming Methodology (Module Descriptor)

Programme: BE in Software Engineering
Credit: 12
Module Tutor: Darshan Subedi/Kamal Acharya
Module Coordinator: Douglas Sim

General Objective

This module introduces students to the fundamental concepts of programming and computational thinking. Starting with the foundations of computing and digital logic, the module progresses through programming fundamentals, data structures, and algorithms. Students will gain a comprehensive understanding of how computers process information, how to implement simple algorithms, and the process of formulating solutions using pseudocode and flowcharts.

Learning outcomes

On completion of this module, the students will be able to:

Explain fundamental concepts in computing, including binary number systems, boolean logic, and basic computer architecture components.
Convert between decimal and binary number systems, and perform basic binary operations.
Analyze and design algorithms using pseudocode and flowcharts to solve computational problems.
Implement basic programming constructs such as variables, operators, conditional statements, loops, and functions.
Apply file operation methods to read from and write to files.
Implement abstract data structures such as trees, graphs, stacks, queues, and linked lists using arrays.
Implement and compare the efficiency of different searching and sorting algorithms on abstract data structures.
Analyze the time and space complexity of algorithms using Big O notation.
Apply graph traversal algorithms to solve pathfinding problems.
Implement dynamic programming solutions for optimization problems.

Learning and teaching approach

Type	Approach	Hours/week	Credit hours
Contact	Lecture	2	30
	Practical	2	30
Independent Study	Assignment	2	30
	Self-study	2	30
Total		8	120

Assessment Approach

Assessment components consist of Continuous Assessment (CA) Theory - 60% and Continuous Assessment (CA) Practical - 40%. The CA Theory will consist of a Mid-Term test (15%), Assignment (30%), Quiz (15%), and CA Practical consists of Whiteboarding.

A. Mid-term Test: (15%)

Students will take a closed book written exam of a 2-hour duration covering subject matter from Unit-I to Unit-III. The exam will be marked out of 15 marks.

B. Programming Assignment: (30%)

The students will be given two programming assignments during the 7th and 12th week. Each assignment will be for 15 marks.

Programming Assignment I

Solve a programming problem using programming constructs, simple data structures, and algorithms. The assignment will be evaluated according to the following criteria:

2 Handling of input file
5 Time & Space Complexity Analysis
3 Code quality and readability
5 Implementation of appropriate data structures and algorithms

Programming Assignment II

Solve a programming problem using the concepts of dynamic programming:

2 Handling of input file
5 Time & Space Complexity Analysis
3 Code quality and readability
5 Implementation of appropriate data structures and algorithms

C. Quiz: (10%)

The students will be required to attempt two closed-book quizzes. Quiz one will test the student's understanding of the subject matter from Unit III and Quiz two will test the student's understanding of the subject matter from Unit IV. Each quiz will be conducted out of 10 marks each for one hour.

D. Practical Work & Report: (10%)

On completion of each weekly practical, a student is required to submit a weekly lab report with an executable file of the practical before the start of the subsequent practical class on a GitHub repository. The report will be written in markdown and submitted along with the executable file for which the format and instructions will be provided by the module tutor. Each report will be evaluated as per the following criteria:

3 Executability of the submission file without errors
2 Compliance with the instruction document
2 Solution approach
2 Use of adequate data structure and algorithm
1 Timely submission

E. Whiteboarding: (35%)

Students will participate in a whiteboarding assessment that consists of two parts: a Written Test and a Viva Voce. This examination will assess the student's ability to solve programming problems, explain their thought process, and optimize their solutions. The examination will be conducted in the 15th Week.

A. Written Test: (10%)

Each student will take a closed-book practical test for 1 hour where the students solve a specific programming problem. The test will be assessed based on the following criteria:

5 Pseudocode
5 Flowchart

B. Viva Voce: (25%)

Following the Practical Test, students will participate in a whiteboarding exercise where they will explain their solution approach for the question they solved in the practical test. They will also be asked to justify their solution methods and discuss potential optimizations. The assessment criteria for the Viva Voce are as follows:

3 Problem Comprehension
8 Technical Implementation
6 Solution Approach
4 Space/Time Analysis
4 Optimizations

Overview of the assessment approaches and weighting

Areas of Assessment	Quantity	Weighting (%)
A. Mid-term Test	1	15
B. Programming Assignment	2	30
C. Quiz	2	10
D. Practical Work & Report	9	10
E. Whiteboarding	1	35
Total	15	100

1.1 Introduction to computing
1.2 Information representation
   1.2.1 Bits and binary numbers
   1.2.2 Binary, octal, and hexadecimal number systems
   1.2.3 Two's complement representation
   1.2.4 Binary operations (addition and subtraction)
   1.2.5 Half adders and full adders
   1.2.6 Multi-bit addition
1.3 Character encoding
   1.3.1 ASCII standard
   1.3.2 Unicode and UTF-8
1.4 Boolean logic and logic gates
   1.4.1 Basic logic gates: AND, OR, NOT
   1.4.2 Composite logic gates: NAND, XOR
1.5 Introduction to Computer Architecture
   1.5.1 Von Neumann Architecture
   1.5.2 Harvard Architecture

Unit II: Programming Fundamentals

2.1 Evolution of programming languages
   2.1.1 Machine language, assembly language, and high-level languages
   2.1.2 Paradigms: imperative, declarative and functional
2.2 Compilers and interpreters
2.3 Computational problem solving
   2.3.1 Pseudocode
   2.3.2 Flowcharts
   2.3.3 Stepwise refinement and top-down design
2.4 Variables and Data Types
   2.4.1 Primitive data types
   2.4.2 Composite/Compound data types
   2.4.3 Type conversion and type casting
2.5 Operators
   2.5.1 Arithmetic operators
   2.5.2 Unary operators
   2.5.3 Assignment operators
   2.5.4 Comparative operators
   2.5.5 Logical operators
   2.5.6 Bitwise operators
   2.5.7 Conditional operators
2.6 Control structures
   2.6.1 Conditional statements (if-else, switch-case)
   2.6.2 Loops (for, while)
   2.6.3 Break and continue statements
2.7 Functions and Scope
   2.7.1 Function definition and invocation
   2.7.2 Parameters and return values
   2.7.3 Local and global scope
   2.7.4 Function Call Stack & Recursion
2.8 Memory Addresses & Pointers
2.9 File operations
   2.9.1 File input/output
   2.9.2 Text and binary file handling

Unit III: Data Structures

3.1 Introduction to storing data
   3.1.1 Static vs dynamic data structures
3.2 Elementary data structures
   3.2.1 Array and its properties
   3.2.2 Array operations and methods
   3.2.3 Multi-dimensional arrays
3.3 Linear Data Types
   3.3.1 List Abstract Data Structure (ADT)
   3.3.2 Stack, Queue, and Deque ADTs in their Linked List Implementations
   3.3.3 Stack and Queue in their (resize-able/circular) Array implementations
3.4 Linked structures
   3.4.1 Singly linked lists
   3.4.2 Doubly linked lists
   3.4.3 Circular linked lists
3.5 Tree data structures
   3.5.1 Binary trees and their properties
   3.5.2 Binary search trees (BST)
      3.5.2.1 BST properties and structure
      3.5.2.2 BST operations: insert, delete, search
      3.5.2.3 Tree traversals: in-order, pre-order, post-order
3.6 Graph data structures
   3.6.1 Graph representations: adjacency matrix and adjacency list
   3.6.2 Weighted and unweighted graphs
   3.6.3 Directed and undirected graphs
3.7 Table/Map ADT Concept
   3.7.1 Definition and Operations
   3.7.2 Unordered map characteristics
   3.7.3 Applications of unordered maps
3.8 Hash Table Implementation
   3.8.1 Hash function design
   3.8.2 Collision resolution: chaining
   3.8.3 Collision resolution: open addressing
   3.8.4 Dynamic resizing and rehashing

Unit IV: Searching & Sorting Algorithms

4.1 Linear Search
   4.1.1 Linear Search algorithm and implementation
   4.1.2 Time and space complexity
4.2 Binary Search
4.3 Depth-First Search (DFS)
   4.3.1 DFS algorithm and implementation
   4.3.2 DFS tree and edge classification
   4.3.3 Time and space complexity
   4.3.4 Applications: cycle detection, topological sorting
4.4 Breadth-First Search (BFS)
   4.4.1 BFS algorithm and implementation
   4.4.2 BFS tree and level order traversal
   4.4.3 Time and space complexity
4.5 Insertion Sort
4.6 Quick Sort
4.7 Bubble Sort

Unit V: Introduction to Computational Problems & Strategies

5.1 Space & Time Complexity, Asymptotic Notation
   5.1.1 Understanding space complexity
   5.1.2 Understanding time complexity
   5.1.3 Big O notation
   5.1.4 Omega and Theta notations
   5.1.5 Analyzing algorithm efficiency
   5.1.6 Comparing algorithm efficiencies
5.2 Arrays & Hashing
   5.2.1 Contains Duplicate problem
   5.2.2 Valid Anagram problem
   5.2.3 Two Sums problem
   5.2.4 Hash table implementations
   5.2.5 Collision resolution techniques
5.3 Two Pointers
   5.3.1 Valid Palindrome problem
   5.3.2 Three Sums problem
   5.3.3 Two pointers technique for array manipulation
   5.3.4 Applications in string problems
5.4 Sliding Window
   5.4.1 Best Time to Buy And Sell Stock problem
   5.4.2 Longest Substring Without Repeating Characters problem
   5.4.3 Fixed-size sliding window technique
   5.4.4 Variable-size sliding window technique
5.5 Stacks & Queues
   5.5.1 Valid Parentheses problem
   5.5.2 Implement Stack using Queue(s) problem
   5.5.3 Stack implementations and applications
   5.5.4 Queue implementations and applications
5.6 Linked List
   5.6.1 Reverse Linked List problem
   5.6.2 Merge Two Sorted Lists problem
   5.6.3 Remove Nth Node From End of List problem
   5.6.4 Singly and doubly linked list operations
5.7 Recursions
   5.7.1 Climbing Stairs problem
   5.7.2 Tower of Hanoi problem
   5.7.3 Understanding recursive algorithms
   5.7.4 Tail recursion optimization
5.8 Bit Manipulation
   5.8.1 Number of 1 Bits problem
   5.8.2 Counting Bits problem
   5.8.3 Reverse Bits problem
   5.8.4 Missing Numbers problem
   5.8.5 Bitwise operations and their applications

List of Practical(s)

Implement a decimal-to-binary converter and basic logic gate simulator
Create a text file analyzer that calculates various statistics using control structures
Implement recursive and iterative Fibonacci sequence generators
Implement linear and binary search algorithms
Implement stack and queue data structures and use them to solve practical problems
Create a singly linked list with basic operations and list manipulation functions
Implement a binary search tree with insertion, deletion, search, and traversal operations
Implement bubble, merge, and quick sort algorithms
Create a graph data structure and implement basic graph traversal algorithms

Reading list

Essential Reading

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms, fourth edition. MIT Press.
Abelson, H. (1996). Structure and interpretation of computer programs. Mit Press.
Bryant, R. E., & O'Hallaron, D. R. (2015). Computer systems: A Programmer's Perspective, Global Edition.

Additional Reading

Simpson, K. (2020). You don't know JS yet: Get Started.
Haverbeke, M. (2018). Eloquent JavaScript, 3rd Edition: A Modern Introduction to Programming. No Starch Press.

Date: August 2024