TOPICS FOR PROJECTS IN DISCRETE STRUCTURES

1. Numerical Methods for Root Finding

 Description: Implement numerical algorithms like Newton's method, bisection
method, or secant method to find roots of equations.
 Math Concept: Calculus, algebra, iterative methods, convergence.
2. Dynamic Programming Algorithms
 Description: Solve problems like the Fibonacci sequence, knapsack problem, or
longest common subsequence using dynamic programming.
 Math Concept: Recurrence relations, combinatorics, and optimization.
3. Fourier Transform and Signal Processing
 Description: Implement Fourier transform algorithms for processing signals or
images.
 Math Concept: Trigonometry, linear algebra, and signal processing.
4. Fractals and Recursive Algorithms
 Description: Create recursive algorithms to generate fractal images like the
Mandelbrot set or Sierpinski triangle.
 Math Concept: Recursion, geometry, and complex numbers.
5. Exploring Relations in Social Networks
 Idea: Model and analyze relationships between people in a social network using
directed graphs. The nodes represent people, and edges represent friendships or
follower relationships.
 What you’ll learn: Graph theory basics, relations, and adjacency matrices.
 Extension: Study properties like transitivity (if A is friends with B, and B is friends
with C, is A friends with C?), and reflexivity in real-world networks (e.g., Twitter,
Instagram).

6. Nash Equilibrium – Introduction to Game Theory

  Project Idea: Simulate simple games (e.g., Prisoner's Dilemma) to explore strategies
and compute Nash equilibria.
 Concepts: Game theory, decision-making, and real-world applications in economics
and computer science.

1. Collatz Conjecture

 Project Idea: Write a program to test the Collatz Conjecture for any positive integer.
For a number nnn:
o If nnn is even, divide it by 2.
o If nnn is odd, multiply it by 3 and add 1.
o Repeat until n=1n = 1n=1.
 Concepts: Sequences, recursion, and conjectures in mathematics.
 Extensions: Visualize the sequence for multiple inputs and analyze patterns or
computational efficiency.

2. Recurrence Relations

 Project Idea: Solve and analyze common recurrence relations, such as Fibonacci or
T(n)=2T(n/2)+nT(n) = 2T(n/2) + nT(n)=2T(n/2)+n. Implement iterative and recursive
solutions.
 Concepts: Recursive functions, dynamic programming, and algorithm analysis.
 Extensions: Explore their role in computational complexity and divide-and-conquer
algorithms.

3. Sylvester’s Sequence

 Project Idea: Write a program to generate Sylvester's sequence:

𝑎1 = 2, 𝑎𝑛+1 = 𝑎𝑛2 − 𝑎𝑛 + 1

 Visualize how the sequence grows and discuss its connection to mathematical concepts
such as Egyptian fractions.

 Concepts: Exponential growth, recursion.

 Extensions: Explore its properties and applications in number theory.

4. Recaman’s Sequence
  Project Idea: Implement Recaman’s sequence:
o Start with 𝑎0 = 0
 For 𝑛 > 0 𝑎𝑛 = 𝑎𝑛−1 − 𝑛 if positive and not already in the sequence; otherwise,
𝑎𝑛 = 𝑎𝑛−1 + 𝑛
 Concepts: Recursion, sequences, and visualization.
 Extensions: Visualize the sequence and investigate its interesting properties, such as
the lack of repetition.

5. Generate Pythagorean Triplets

 Project Idea: Write a program to generate Pythagorean triplets (a,b,c)

𝑎2 + 𝑏 2 = 𝑐 2

o Concepts: Number theory, geometry.

 Extensions: Explore primitive and non-primitive triplets and their geometric

significance.

6. Monte Carlo Methods

 Project Idea: Write a program to approximate the value of π by randomly generating

points within a square and counting how many fall inside a circle inscribed within that
square.
 Concepts: Probability, randomness, and real-world applications (e.g., in simulations and
risk analysis).
 Extensions: Apply Monte Carlo methods to estimate areas, integrals, or other problems
involving probability.

7. Farey Sequence and Applications

 Project Idea: Write a program to generate the Farey sequence of order 𝑛, which consists
of all unique fractions between 0 and 1 with denominators up to 𝑛.
 Concepts: Fractions, number theory, and rational approximations.
 Extensions: Explore applications in rational approximation, music theory, or continued
fractions.

8. Normal Distribution (Gaussian Distribution)

 Definition: The normal distribution is bell-shaped and symmetric around the mean,
characterized by two parameters: mean (μ) and standard deviation (σ).
 Application:
o Analyze natural phenomena such as heights, weights, or test scores.
o Use in machine learning for Gaussian Naive Bayes classification.
 Project Idea: Simulate a normal distribution and visualize its probability density
function (PDF). Fit data to a normal distribution and calculate probabilities for given
ranges.

 Definition: A discrete probability distribution representing two possible outcomes (e.g.,

success or failure), with probability 𝑝 for success.
 Application:
o Used in binary events like coin flips or yes/no outcomes.
o Basis for other distributions like Binomial.
 Project Idea: Simulate repeated trials (e.g., flipping a coin) and calculate the probability
of success over multiple iterations.

9. General Applications in Data Analysis

 1. Hypothesis Testing: Use distributions like Normal or t-distribution to test statistical

hypotheses (e.g., comparing means).
 2. Simulation: Generate synthetic data to test algorithms.
 3. Machine Learning: Distributions underpin models like Gaussian Mixture Models
(GMMs) or Bayesian networks.
 4. Reliability Analysis: Use Gamma or Exponential distributions to model the reliability
of systems.

10. Boolean Functions

 Representing Boolean Functions

 Logic Gates

11. Trees
 Introduction to Trees
 Applications of Trees
12. Minimum Spanning Tree

 Project Idea: Implement Kruskal’s and Prim’s algorithms to find the Minimum
Spanning Tree (MST) of a graph. Compare their efficiency and output.
 Concepts:
o Graph connectivity, greedy algorithms.
 Extensions: Apply MSTs to network design problems like building minimum-cost
communication networks.
 13. Algorithms and Complexity

 Algorithm Design and Analysis: Mathematics is critical for developing and analyzing
algorithms.
o Examples: Big-O notation (asymptotic analysis), graph algorithms, and divide-
and-conquer methods.
 Computational Complexity: This branch of mathematics helps classify problems based
on their solvability and efficiency (e.g., P, NP, and NP-complete problems).
o Applications: Cryptography, scheduling, and optimization.

14. Artificial Intelligence and Machine Learning

 Mathematical Foundations: AI and ML use mathematical concepts for modeling and

prediction.
o Linear algebra: Representing and manipulating datasets (e.g., feature vectors,
matrices).
o Probability and statistics: Decision-making under uncertainty, Bayesian networks,
and Markov models.
o Calculus: Optimization algorithms for training models (e.g., gradient descent).
 Applications: Natural language processing, computer vision, and recommendation
systems.

15. Binary Mathematics:

 Binary mathematics is the heart of the computer and an essential math field for computer
programming. For all mathematical concepts, the binary number system uses only two
digits, 0 and 1. It simplifies the coding process and is essential for low-level instructions
used in hardware programming. Computers store data using the binary system. The
information we store on computers, from pictures to games and even videos, is stored
using the binary number system.

16. Linear Algebra:

Linear Algebra is the language of machine learning. The heartbeat of the computer is in
linear algebra. This branch of mathematics provides concepts crucial to many areas of
computer science, including graphics, image processing, cryptography, machine learning,
computer vision, optimization, graph algorithms, quantum computation, computational
biology, information retrieval and web search. Linear algebra is what makes your video
games look so breathtaking, and answers whatever questions you may be asking!
 17. Applied Mathematics

 Fourier Transform Applications: Implement Fourier transforms for image compression

or sound signal analysis.
 Game Theory in Decision Making: Create simulations to demonstrate Nash equilibria
in various scenarios.
 Chaos Theory and Fractals: Explore the mathematics behind fractals and implement
fractal generators.

18. Computational Number Theory

 Prime Number Theorems: Develop a program to find large primes and verify their
properties.
 Modular Arithmetic Applications: Use modular arithmetic in coding problems like hash
functions or modular exponentiation.

19. Fast Fourier Transform (FFT)

 Purpose: Computes the Discrete Fourier Transform (DFT) efficiently.

 Application: Signal processing, image compression, audio analysis, and solving
differential equations.

o Represented as structures that can be mapped over, like lists or trees, in functional
programming.
o Generalize monads for scenarios where computation involves combining
independent effects.

20. Finite Automata

 Deterministic Finite Automata
 Pumping Lemma
 Regular Expressions and Kleene’s Theorem

21. Induction and Recursion

 Mathematical Induction
 Strong Induction and Well-Ordering
 Recursive Definitions and Structural Induction.
 Recursive Algorithms
 Program Correctness
ii.