• About

Sketches, polytopes

~ Online algorithms, optimization, estimation

Sketches, polytopes

Category Archives: Java

2-butterfly derangement

10 Saturday Dec 2016

Posted by umayrh in Algorithms, Java, Mathematics, Permutations, Switching networks

≈ Leave a comment

The hallmark of the Cooley-Tukey algorithm for  Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

res3

Three butterflies – FFT flow graph, shuffling network, and a nonblocking interconnect

Continue reading →

Maximum weighted independent set – connected component

09 Friday Dec 2016

Posted by umayrh in Algorithms, BitSet, Graph Theory, Independent sets, cliques, colors, Java, Mathematics

≈ Leave a comment

coloringpeteresen2Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight. Continue reading →

Maximum weighted independent set – singletons and forest

06 Tuesday Dec 2016

Posted by umayrh in Algorithms, BitSet, Combinatorics, Dynamic programming, Graph Theory, Independent sets, cliques, colors, Java, Mathematics

≈ Leave a comment

Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.

  1. At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
  2. Any two restaurants must be at least 2 miles apart.

clebschgraphk16_800 Continue reading →

Generalized heaps

27 Thursday Oct 2016

Posted by umayrh in Algorithms, Data structures, Heaps, Java, Mathematics

≈ Leave a comment

screen-shot-2016-10-27-at-10-31-39-amMin-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

Continue reading →

Rational numbers in decimal

27 Thursday Oct 2016

Posted by umayrh in Algorithms, Java, Mathematics, Number Theory

≈ Leave a comment

In decimal representation, rational numbers either terminate after a finite number of digits or produce a repeating sequence. Conversely, any repeating decimal can be converted into a rational number e.g. (10 * 0.333.. – 0.333…) / 9 = 1/3.

Continue reading →

IP possibilities

24 Thursday May 2012

Posted by umayrh in Algorithms, Combinatorics, Java

≈ Leave a comment

A problem I was asked: suppose a file that stored many valid IPv4 addresses was corrupted such that all dot in the addresses were removed. Given such a corrupt IP, infer all possible corresponding IP addresses. For example, given 12345, all possible addresses are: 12.3.4.5, 1.23.4.5, 1.2.34.5 and 1.2.3.45. The hint that recursion should be used made the problem easier:

Continue reading →

Sorting primer

20 Sunday May 2012

Posted by umayrh in Algorithms, Arrays, Lists & Queues, Java

≈ Leave a comment

A quick overview of several important comparison-based sorting algorithms:

Sorting technique Time (avg) Time (worst) Memory
Insertion sort O(N^2) O(N^2) O(1)
Heap sort O(NlgN) O(NlgN) O(1)
Merge sort O(NlgN) O(NlgN) O(N)
Quick sort O(NlgN) O(n^2) O(lgN)

Continue reading →

Aggregation Algorithms Arrays, Lists & Queues Awk BitSet Combinatorics Computational economics Convex geometry Convex optimization Database Data structures First-order methods Graph Theory Heaps Independent sets, cliques, colors Java Linear Algebra Mass deletion Mathematicians Mathematics Number Theory Perl Probabilistic Models & Stochastic Processes Programming Python R Resource allocation Robust Estimation Shell SQL

Blogroll

  • AMS What's Happening
  • IEEE CSS Lectures
  • IMA @ U. Minn.
  • IPAM @ UCLA
  • MOS Optima
  • Proceedings of NAS
  • Quanta
  • R-bloggers
  • SAMSI
  • SIAM News
  • SIGECom Exchanges
  • Simons Institute

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 913 other followers

Follow Sketches, polytopes on WordPress.com
April 2021
M T W T F S S
 1234
567891011
12131415161718
19202122232425
2627282930  
« Aug    

Categories

Blogs I Follow

  • SAMSI Blog
  • Markus Weimer
  • matthew arcus
  • Igor Pak's blog
  • Machinations
  • Karussell
  • Not so Great Ideas in Theoretical Computer Science
  • Abhinav Aggarwal
  • Hydrobates
  • The Operatunist
  • Relax and Conquer
  • Sam Clifford
  • Blog – dstillery
  • A Computer Scientist in a Business School
  • Math ∩ Programming
  • Sketches of Topology
  • Raanan Bar-Cohen
  • Mathematics of Planet Earth
  • AI and Social Science - Brendan O'Connor
  • Adventures in Data Land

Create a free website or blog at WordPress.com.

SAMSI Blog

Exploring Statistics and Applied Mathematical Research

Markus Weimer

matthew arcus

Igor Pak's blog

Views on life and math

Machinations

Distributed Algorithms and Security

Karussell

Thoughts about Java and more

Not so Great Ideas in Theoretical Computer Science

A student blog of MIT CSAIL Theory of Computation Group

Abhinav Aggarwal

Learn. Master. Innovate.

Hydrobates

A mathematician thinks aloud

The Operatunist

Musings on opera, ballet and theatre

Relax and Conquer

A math research blog by Afonso S. Bandeira

Sam Clifford

Postdoctoral Fellow, Bayesian Statistics, Aerosol Science

Blog – dstillery

Online algorithms, optimization, estimation

A Computer Scientist in a Business School

Online algorithms, optimization, estimation

Math ∩ Programming

Sketches of Topology

visualizations of low dimensional topology

Raanan Bar-Cohen

all about the Partnerships

Mathematics of Planet Earth

Online algorithms, optimization, estimation

AI and Social Science - Brendan O'Connor

Online algorithms, optimization, estimation

Adventures in Data Land

Online algorithms, optimization, estimation

Cancel

 
Loading Comments...
Comment
    ×
    Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
    To find out more, including how to control cookies, see here: Cookie Policy