NaijaCoder 2024 Syllabus

It’s that time of the year!

The NaijaCoder 2024 camp is scheduled to take place in Abuja, Nigeria and Lagos, Nigeria. The Abuja camp is in collaboration with Olumawu School in Abuja. We plan on using their facilities (including classrooms and computer labs) to host the students on a daily basis. At a very early age, my elder sisters and I attended Olumawu School for some time; this is the main reason the headmaster is allowing us to use their facilities — taking advantage of our alumni privileges. The Lagos camp is in collaboration with the AI and Robotics Lab of the University of Lagos, directed by Dr. Chika Yinka-Banjo. I’m very excited to kick off these (and hopefully more) collaborations with the University of Lagos, as NaijaCoder builds more roots within the Nigerian educational system.

Dates (assuming the scheduled protests this August do not disrupt our activities):

  1. Abuja: 12th of August to the 23rd of August.
  2. Lagos:  19th of August to the 30th of August

This year, we have secured funding from many organizations who believe in our mission, including:

Also, this year’s MIT Davis Peace Prize was awarded to MIT junior Victory Yinka-Banjo who is using the grant to fund her activities in Lagos for the NaijaCoder 2024 program in Lagos. Congrats Victory! My participation in NaijaCoder remains supported (through a Simons Junior Fellowship grant) by the Simons Foundation. Thanks to all our funders for supporting the next generation of scientists, engineers, mathematicians.

Syllabus Updates

This year, we have updated the syllabus significantly! Day 1, as in last year, would start slow and steady with a keynote by Prof. Jelani Nelson, the founder of AddisCoder (which inspires NaijaCoder) and the lead advisor of NaijaCoder! Then we will introduce them to the main textbook (CLRS) [1]. Then we plan on spending the afternoon going through some basics of the python programming language (including variable naming convention and good commenting practice). Obviously, the plan is not to cover all the basics of computer programming and algorithms in less than a month. But to provide enough material and resources so they can keep learning on their own.

Summaries of NaijaCoder Lectures (Days 2 to 10)

Day 2 Summary: Functions and Modules

  • Objective: Understand functions and their importance in programming.
  • Topics Covered:
    • Defining and calling functions.
    • Function parameters and return values.
    • Scope and lifetime of variables.
    • Lambda functions.
    • Creating and using modules.
  • Activities: Writing and using functions, creating modules, and hands-on exercises to solidify understanding.

Day 3 Summary: For Loops and Recursion

  • Objective: Learn to use for loops and understand recursion.
  • Topics Covered:
    • For loops: syntax, examples, break and continue, nested loops, enumerate, and zip.
    • Recursion: basic concepts, base and recursive cases, examples (factorial, Fibonacci sequence), and performance considerations.
  • Activities: Exercises on for loops and recursion, including practical problems.

Day 4 Summary: Data Structures – Lists and Dictionaries

  • Objective: Introduce lists and dictionaries, two fundamental data structures.
  • Topics Covered:
    • Lists: creation, indexing, slicing, methods (append, remove, etc.), list comprehensions.
    • Dictionaries: creation, accessing values, adding/removing key-value pairs, dictionary methods.
  • Activities: Practical exercises on using lists and dictionaries to solve problems.

Day 5 Summary: Object-Oriented Programming (OOP) Basics

  • Objective: Introduce OOP concepts.
  • Topics Covered:
    • Classes and objects.
    • Attributes and methods.
    • The self keyword.
    • Inheritance and polymorphism.
  • Activities: Exercises on creating classes, instantiating objects, and applying inheritance.

Day 6 Summary: Growth of Functions

  • Objective: Understand the growth of functions and asymptotic notation.
  • Topics Covered:
    • Growth functions (linear, quadratic).
    • Asymptotic notations: Big O, Omega, Theta.
    • Practical use in algorithm analysis.
    • Small o and omega notations.
  • Activities: Exercises on identifying and verifying notations and matching functions with appropriate notations.

Day 7 Summary: Searching Algorithms

  • Objective: Learn basic and efficient searching algorithms.
  • Topics Covered:
    • Linear Search: Simple sequential search with time complexity (O(n)).
    • Binary Search: Efficient search on sorted lists with time complexity (O(\log n)).
  • Activities: Exercises on implementing linear and binary search, counting occurrences, and finding elements.

Day 8, 9 Summary: Sorting Algorithms

  • Objective: Learn various sorting algorithms.
  • Algorithms Covered:
    • Bubble Sort: Simple but inefficient for large datasets.
    • Selection Sort: Inefficient but easy to implement.
    • Insertion Sort: Efficient for small or nearly sorted datasets.
    • Merge Sort: Efficient and stable, suitable for large datasets.
    • Quick Sort: Efficient and in-place, often faster than Merge Sort in practice.
  • Activities: Implement and compare these sorting algorithms.

Day 10 Summary: Recap, Exams, Review, Awards

Looking forward to the camp!

[1] “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

PODS/SIGMOD 2024 in Santiago, Chile

I attended my first research conference in 2016 in San Francisco, California. In general, I had a nice time and made new connections with fellow students and more established researchers. Then, I had not begun my PhD studies and was not sure what direction my research would take me to! Now, I’ve come full circle and hope to more regularly attend database conferences like PODS/SIGMOD. Recently, I traveled to Santiago, Chile for PODS/SIGMOD.

My blog post can’t do justice to summarizing all the amazing talks/sessions that I attended. Check out the conference website that details the PODS/SIGMOD keynotes and special events.

Leftover Hash Lemma

Recently, I’ve been investigating computational notions of entropy and had to use the Leftover Hash Lemma. (A variant of this lemma is stated below) I first encountered the Lemma several years ago but didn’t have to use it for anything… until now!

The lemma is attributed to Impagliazzo, Levin, and Luby [1]. A corollary of the lemma is that one can convert a source of (high-enough) Rényi entropy into a distribution that is uniform (or close to uniform). Before stating the Lemma, I’ll discuss a few different notions of entropy, including the classic Shannon Entropy, min-entropy, max-entropy, and so on. See [2] for many different applications for the entropy measures.

Entropy Measures

Consider the random variable X. We use x\xleftarrow{R} X to denote that the element x is randomly drawn from X. Denote its support by Supp(X). Define the sample entropy of x with respect to X as H_X(x) = \log\frac{1}{\mathbb{P}[X=x]}. The sample entropy measures how much randomness is present in the sample x when generated according to the law/density-function of X. Also, let H_X(x) = \infty when x\notinSupp(X). Then we can state the entropy measures in terms of the sample entropy:

  • Shannon Entropy: H(X) = \mathbb{E}_{x\xleftarrow{R} X}[H_X(x)]
  • Min-Entropy: H_\infty(X) = \min_{x\in\text{Supp}(X)}H_X(x)
  • Rényi Entropy: H_2(X) = -\log\sum_{x\in\text{Supp}(X)}\mathbb{P}_X(x)^2
  • Max-Entropy: H_0(X) = \log(|\text{Supp}(X)|)

How should we interpret these measures? The min-entropy can be seen as a worst-case measure of how “random” a random variable is. The Rényi entropy measure, intuitively, measures how “collision-resistant” a random variable is (i.e., think hash functions). In my opinion, max-entropy does not give much information, except for how large the support of a random variable is. These entropy measures are related by this inequality:

H_\infty(X)\leq H_2(X) \leq H(X) \leq H_0(X)

The inequality above is tight if and only if X is uniformly distributed on its support. The statement of the lemma below uses universal hash functions. Here is a definition:

A function family \mathcal{H} = \{h:\mathcal{D}\mapsto\mathcal{R}\} is two-universal if \forall x\neq x'\in\mathcal{D}, the following holds: \mathbb{P}_{h\xleftarrow{R}\mathcal{H}}[h(x) = h(x')]\leq 1/|\mathcal{R}|.

The Lemma

Statement: Let X be a random variable over \{0, 1\}^n with H_2(X)\geq k. Consider the two-universal function family \mathcal{H} = \{g:\{0, 1\}^n\mapsto\{0, 1\}^m\}. Then for any H\xleftarrow{R}\mathcal{H}, the statistical distance between (H, H(X)) and (H, \mathcal{U}_m) is at most \frac{1}{2}\cdot 2^{(m-k)/2}.

One can interpret the statement above as saying that you can convert a random variable with high-enough Rényi entropy into a random variable that is very close to uniform.

References

[1]  Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1989). Pseudo-random Generation from one-way functions.

[2] Iftach Haitner and Salil Vadhan. The Many Entropies in One-Way Functions, pages 159–217. Springer International Publishing, 2017